You are not logged in. Please login at www.codechef.com to post your questions!

×

NPLFSGL-Editorial

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.

asked 12 Nov '17, 12:29

manjunath1996's gravatar image

4★manjunath1996
1287
accept rate: 8%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×66
×8

question asked: 12 Nov '17, 12:29

question was seen: 184 times

last updated: 12 Nov '17, 12:29