11987 - Almost Union-Find
Solution Description : Union-Find problem You can solve this problem using Union-Find algorithm with some extra work for command 2. You can use three array set[] for union find, Element[] for number of element in parent and Sum[] for sum of element in parent. For n=5 at first set value to three arrays. 1= set:-1 Element:1 Sum:1 2= set:-1 Element:1 Sum:2 3= set:-1 Element:1 Sum:3 4= set:-1 Element:1 Sum:4 5= set:-1 Element:1 Sum:5 Here set[i]=-1 indicate parent node. For command: 1 1 2 (Simple Union-Find) 1= set: 2 Element:0 Sum:0 (1 is child of 2) 2= set:-1 Element:2 Sum:3 (2 is a parent of 1) Sum[2] = Sum[2]+Sum[1] 3= set:-1 Element:1 Sum:3 4= set:-1 Element:1 Sum:4 5= set:-1 Element:1 Sum:5 For command: 2 3 4 (Move command) In previous stage 3 is a parent node and have 1 element so, you can use simple Union-Find 1= set: 2 Element:0 Sum:0 2= set:-1 Element:2 Sum:3 3= set: 4 Element:0 Sum:0 4= set:-1 Element:2 Sum:7 5= set:-1 Element:1 Sum:5 For command: 1 3 5 (Simple Union-Find) 1= set:2 Element:0 Sum:0 2= set:-1 Element:2 Sum:3 3= set:4 Element:0 Sum:0 4= set:5 Element:0 Sum:0 5= set:-1 Element:3 Sum:12 For command: 2 4 1 (Move command) 1= set: 2 Element:0 Sum:0 2= set:-1 Element:3 Sum:7 3= set: 5 Element:0 Sum:0 (This is the extra work, 4 move to new group, but in old group 4 is the parent of 3. So, you need to change all the value of set[] if set[i]==4 by group leader (Here group leader 5) of old group then move the element 4 to new group) 4= set: 2 Element:0 Sum:0 5= set:-1 Element:2 Sum:8 For command: 2 5 4 (Move command) 1= set: 2 Element:0 Sum:0 2= set:-1 Element:4 Sum:12 3= set:-1 Element:1 Sum:3 (New group leader) 4= set: 2 Element:0 Sum:0 5= set: 2 Element:0 Sum:0 (There is another extra work, 5 move to new group, but in old group 5 is the group leader. First you need to find new group leader in old group. Then you need to change all the value of set[] if set[i]==5 by the new group leader (Here new group leader 3) of old group then move the element 4 to new group). |
||||||||||