Tuesday, January 13, 2015

Codeforces Round 285 (Div. 2 C or Div. 1 A) - Misha and Forest

Problem Statement:
501C - Misha and Forest

Solution:
An interesting mix of tree structure and linear algebra. Since we are given the pair $$(\text{degree}_v, s_v)$$ for each v, we can approach it in an intuitive manner:
1. We will maintain a graph G with vertices v but with no edges just yet. So initially all vertices in G has no neighbouring vertices.
2. Iteratively, we would like to find a vertex v such that the difference between the number of neighbours it currently has and $$\text{degree}_v$$ is at most 1. This means that v is short of one vertex. Furthermore, this means that we can determine what vertex is that exactly in O(M) where M is the number of adjacent vertices v currently has, as follows:

We have $$s_v = \text{XOR of all current neighbours of v } u \oplus v'$$ where v' is the node we want to find. If we XOR both left hand side and right hand side with $$\text{XOR of all current neighbours of v}$$, we will find v'!

We can perform 2 in $$O(N\lg{N}$$ using heap structure such as priority queue, and since the final graph is guaranteed to be a tree, the amortized number of operations we need to calculate all the v' is $$O(V)$$. A nice problem :)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

priority_queue<pair<int,int> > st;
vector<pair<int,int> > ans;
int degree[70000], s[70000];
int N;
int main(){
int u,v,w;
scanf("%d",&N);
for(int i=0;i<N;++i){
scanf("%d %d",&u,&v);
st.push(make_pair(-u,i));
degree[i] = u;
s[i] = v;
}
while(!st.empty()){
u = st.top().second;
v = -st.top().first;
w = s[u];
st.pop();