Submission #234628

#	Time	Username	Problem	Language	Result	Execution time	Memory
234628		crossing0ver	Parachute rings (IOI12_rings)	C++17	100 / 100	3772 ms	78744 KiB

rings

#include<bits/stdc++.h>
using namespace std;
int n,cycle_size,cycles;
vector<int> adj[1000001];
bool flag = 1;
int sz[1000001],SZ[1000001], P[1000001] , ans, center = -1,help,seen[1000001],change,d;
bool bad[1000001],good[1000001];
set<int> more_than4;
int par(int a) {
	if (a != P[a]) 
		return P[a] = par(P[a]);
	return a;
}
void join(int a,int b) {
	int x = par(a);
	int y = par(b);
	if (x == y) return;
	if (SZ[x] > SZ[y]) swap(x,y);
	P[x] = y;
	SZ[y] += SZ[x];
}

void Init(int N) {
	ans = n = N;
	for (int i = 0 ; i < n; i++)
		P[i] = i,good[i] = SZ[i] = 1;
}

int vis[1000001];

void dfs (int v,int p,int X) {
	if (sz[v] >= 3) 
		flag = 0;
	vis[v] = help;
	for (int i: adj[v]) {
		if (i == p || i == X) continue;
		if (vis[i] == help) {
			flag = 0;
		}else dfs(i,v,X);
	}
}
bool check(int v) {
	if (!good[v]) return 0;
	help++;
	flag = 1;
	for (int i : adj[v]) sz[i]--;
	for (int i = 0; i < n; i++)
		if (i != v && help != vis[i]) dfs(i,-1,v);
	for (int i : adj[v]) sz[i]++;
	good[v] = flag;
	return flag; 
}
vector<int> dangerous;
void add(int x) {
	if (bad[x]) return;
	bad[x] = 1; dangerous.push_back(x);
}
void Link(int A, int B) {
	if (ans == 0) return;
	if (center != B)
	sz[A]++;
	if (center != A)
	sz[B]++;
	adj[A].push_back(B);
	adj[B].push_back(A);
	if (center !=  -1) {
		if (!d) {
			for (int i = 0 ; i < n; i++)
			P[i] = i, SZ[i] = 1,sz[i]= 0;
		for (int i = 0; i < n; i ++)
			if (i != center)
			for (int j : adj[i])
				if (j != center)
			  		join(j,i),sz[i]++;
					  d  = 1;	
			  	}
		if (A != center && B != center) {
			if (sz[A] >= 3 || sz[B] >= 3) {ans = 0; return;}
			int x = par(A), y = par(B);
		join(A,B);
		if (sz[A] == 1 || sz[B] == 1) return;
		if (x != y)  return;
		ans = 0; return;
		}
	} 
	if (sz[A] == 3) {change = 1;add(A);for (int i:adj[A]) add(i);}
	if (sz[B] == 3) {change = 1;add(B);for (int i : adj[B]) add(i);}
	if (sz[A] >= 4) more_than4.insert(A),change = 1;
	if (sz[B] >= 4) more_than4.insert(B),change = 1;
	if (more_than4.size() >= 2) { ans = 0; return; }
	if (A == center || B == center ) { change = 0; return;}
	int x = par(A), y = par(B);
	join(A,B);
	if (x != y && sz[A] <= 2 && sz[B] <= 2 ) return;
	if (more_than4.size()) center = *more_than4.begin(); 
	if (A == center) { ans = check(A); return;}
	if (B == center) { ans = check(B); return;}
	if (sz[A]>= 3 || sz[B] >= 3) {
		if (center != -1 ) {
			ans = check(center);
			return;
		}
		int t = 0;
		for (int j : dangerous) t += check(j);
		ans = t;
		return;
	}
	if (sz[A] == 1 || sz[B] == 1) return;
	if (x == y && sz[A] == 2 && sz[B] == 2) {
		if (dangerous.empty()) {
			if (cycles) { ans = 0; return;}
			   cycles = 1;
			   cycle_size = SZ[par(A)];
			   ans = cycle_size;
			   return ;
		} else {
			int t = 0;
			if (center != -1 ){
				ans = check(center);
				return;
			}
		for (int j : dangerous) t += check(j);
		ans = t;
		return;
		}
	}	
}
int CountCritical() {
	return ans;
}

Compilation message (stderr)

rings.cpp: In function 'void Init(int)':
rings.cpp:26:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   P[i] = i,good[i] = SZ[i] = 1;
                      ~~~~~~^~~

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