NPLFSGL-Editorial

general
,
1

PROBLEM LINK:

Practice
Contest

Author: Vinod
Tester: Vinod
Editorialist: Manjunath

DIFFICULTY:

MEDIUM

PREREQUISITES:

graph,xor propery,union disjoint

PROBLEM:

batch power of graph is defined as sum of xor of all connected vertices.Each day one edge is being blocked (consider as removed).We have to find batch power on each day after removal.

QUICK EXPLANATION:

Instead of blocking, consider each day we are unblocking the edges. Then it is easy to solve this problem.so suppose previously 2 connected components x,y were there which were just connected by unblocking current edges.Then answer changes as ans=prev_ans-(xor(x)+xor(y))+xor(x,y),where (x,y) denoted connected graph of x,y vertices.We can convert the actual problem to this variation by considering unblocking of edges from last day to the first day.

EXPLANATION:

Instead of blocking, consider each day we are unblocking the edges. Then it is easy to solve this problem.so suppose previously 2 connected components x,y were there which were just connected by unblocking current edges.Then answer changes as ans=prev_ans-(xor(x)+xor(y))+xor(x,y),where (x,y) denoted connected graph of x,y vertices.We can convert the actual problem to this variation by considering unblocking of edges from last day to the first day.


make each vertex as a disjoint set.
value of disjoint set is xor of all vertices in that set.
answer[m]=sum 
for(int i=m;i>=1;i--){
    //u-v is being unblocked
    if(set(u)==set(v)){
      ans[i-1]=ans[i];
    }
    else{
    ans[i-1]=ans[i]-value(set(u))-value((set(v));
    union(u,v);
    value(set(u))=value(set(u))^value((set(v));
    ans[i-1]+=value(set(u));
    }
}

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.