Submission #36817

#	Time	Username	Problem	Language	Result	Execution time	Memory
36817		mohammad_kilani	Parachute rings (IOI12_rings)	C++98	100 / 100	1974 ms	113164 KiB

rings

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n , comp[N], mx , adj[N] , ans = 0 , cycles = 0 , vis[N] , vi = 0 , comp2[4][N] , con1[4][N] , con2[4][N] , qu[N] , in[N] , idx = 0 , u , vv;
vector< int > g[N];
vector< pair<int,bool> > v;
vector< pair<int,int> > v2;


void Init(int N_) {
  n = N_;
  ans = n ;
  for(int i=0;i<n;i++) 
  	comp[i] = i;
  mx = 0 ;
  cycles = 0 ;
}


void DFS(int node,int prnt,int last){
	while(true){
		ans++;
		if(node == last) return;
		for(int i=0;i<(int)g[node].size();i++){
			if(g[node][i] != prnt){
				prnt = node;
				node = g[node][i];
				break;
			}
		}
	}
}


void make(int u){
	v.push_back(make_pair(u,true));
	for(int i=0;i<(int)g[u].size();i++){
		v.push_back(make_pair(g[u][i],true));
	}
	ans = 0 ;
	int st = 0 , en = 1 , num = 0 , node = 0;
	for(int i=0;i<(int)v.size();i++){
		vi++;
		for(int j=0;j<n;j++){
			if(j == v[i].first || vis[j] == vi) continue;
			con1[i][j] = con2[i][j] = -1;
			st = 0 , en = 1 , num = 0 , node = j;
			qu[0] = j;
			vis[j] = vi;
			while(st < en){
				node = qu[st++];
				comp2[i][node] = j;
				num = 0 ;
				for(int k=0;k<(int)g[node].size();k++){
					num += (g[node][k] != v[i].first);
					if(vis[g[node][k]] == vi || g[node][k] == v[i].first) continue;
					qu[en++] = g[node][k];
					vis[g[node][k]] = vi;
				}
				if(num < 2){
					if(con1[i][j] == -1) con1[i][j] = node; else con2[i][j] = node;
				}
			}
			if(con1[i][j] == -1){
				v[i].second = false;
				break;
			}
			if(con2[i][j] == -1) con2[i][j] = con1[i][j];
		}
		ans += v[i].second;
	}
}

void Link(int a, int b) {
	if(ans == 0) return;
	if(mx < 3){
		u = a;
		idx = 0 ;
		while(u != comp[u]){
			in[idx++] = u;
			u = comp[u];
		}
		while(idx > 0){
			idx--;
			comp[in[idx]] = u;
		}
		vv = b;
		idx = 0 ;
		while(vv != comp[vv]){
			in[idx++] = vv;
			vv = comp[vv];
		}
		while(idx > 0){
			idx--;
			comp[in[idx]] = vv;
		}
		adj[a]++;
		adj[b]++;
		g[a].push_back(b);
		g[b].push_back(a);
		if(adj[a] == 3){
			mx = 3;
			make(a);
			return ;
		}
		if(adj[b] == 3){
			mx = 3;
			make(b);
			return;
		}
		if(u == vv){
			if(cycles > 0){
				ans = 0;
				return ;
			}
			cycles++;
			ans = 0 ;
			DFS(a,b,b);
		}
		else{
			comp[u] = vv;
		}
		return ;
	}
	for(int i=0;i<(int)v.size();i++){
		if(v[i].second == false) continue;
		if(a == v[i].first || b == v[i].first){
			adj[v[i].first]++;
			if(adj[v[i].first] > 3 && v.size() > 1){
				int cur = v[i].first;
				ans = 1;
				v.clear();
				v.push_back(make_pair(cur,1));
				break;
			}
			continue;
		}
		u = comp2[i][a];
		idx = 0;
		while(u != comp2[i][u]){
			in[idx++] = u;
			u = comp2[i][u];
		}
		while(idx > 0){
			idx--;
			comp2[i][in[idx]] = u;
		}
		vv = comp2[i][b];
		idx = 0;
		while(vv != comp2[i][vv]){
			in[idx++] = vv;
			vv = comp2[i][vv];
		}
		while(idx > 0){
			idx--;
			comp2[i][in[idx]] = vv;
		}
		if(u == vv){
			v[i].second = false;
			ans--;
			continue;
		}
		if(a != con1[i][u] && a != con2[i][u]){
			v[i].second = false;
			ans--;
			continue;
		}
		if(b != con1[i][vv] && b != con2[i][vv]){
			v[i].second = false;
			ans--;
			continue;
		}
		comp2[i][u] = vv;
		if(a == con1[i][u] && b == con1[i][vv]){
			con1[i][vv] = con2[i][u];
		}
		else if(a == con2[i][u] && b == con1[i][vv]){
			con1[i][vv] = con1[i][u];
		}
		else if(a == con1[i][u] && b == con2[i][vv]){
			con2[i][vv] = con2[i][u];
		}
		else if(a == con2[i][u] && b == con2[i][vv]){
			con2[i][vv] = con1[i][u];
		}
	}
}

int CountCritical() {
  return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 14 / 14
• Subtask 5: 31 / 31