Submission #1016054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016054		NintsiChkhaidze	Parachute rings (IOI12_rings)	C++17	100 / 100	771 ms	119276 KiB

rings

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
using namespace std;

const int N = 1e6 + 5;
vector <int> cycles,v[N];
vector <pii> edges;
int deg[N],n,nodes,p[N];
bool crit;
int critical[7],m,fail[7],degree[7][N];
int pp[7][N],sz[N];

void Init(int N_) {
	crit=0;
  n = N_;
  for (int i = 0; i < n; i++)
  	p[i] = i,sz[i] = 1;
}

int P(int x){
	if(x==p[x]) return x;
	return p[x]=P(p[x]);
}

void dsu(int x,int y){
	int px=P(x),py=P(y);
	if (px == py){
		cycles.pb(sz[px]);
		return;
	}
	
	p[py] = px;
	sz[px] += sz[py];
	sz[py] = 0;
}

int PP(int i,int x){
	if(pp[i][x] == x) return x;
	return pp[i][x] = PP(i,pp[i][x]);	
}

void dsuu(int i,int x,int y){
	int px=PP(i,x),py=PP(i,y);
	if (px == py){
		fail[i] = 1;
		return;
	}
	
	pp[i][py] = px;
}

void addedge(int i,int x,int y){
	if (fail[i]) return;
	if (x == critical[i] || y == critical[i]) return;
	degree[i][x]++;
	degree[i][y]++;
	
	if (degree[i][x] > 2 || degree[i][y] > 2) {
		fail[i] = 1;
		return;
	}
	
	dsuu(i,x,y);
}

void Link(int A, int B) {
	bool old = crit;
	deg[A]++;
	deg[B]++;
	v[A].pb(B); v[B].pb(A);
	edges.pb({A,B});
	
	if (!crit){
		if (deg[A] >= 3){
			crit = 1;
			if (deg[A] >= 4){
				m = 1;
				critical[1] = A;
			} else{
				m = 4;
				critical[1] = A;
				critical[2] = v[A][0];
				critical[3] = v[A][1];
				critical[4] = v[A][2];
			}
			
		}
	}
	
	if (!crit){
		if (deg[B] >= 3){
			crit = 1;
			if (deg[B] >= 4){
				m = 1;
				critical[1] = B;
			} else{
				m = 4;
				critical[1] = B;
				critical[2] = v[B][0];
				critical[3] = v[B][1];
				critical[4] = v[B][2];
			}
			
		}
	}
	
	if (old){
		for (int i = 1; i <= m; i++){
			addedge(i,A,B);
		}
	}else if (!old && crit){
		for (int i = 1; i <= m; i++){
			fail[i] = 0;
			for (int j = 0; j < n; j++){
				pp[i][j] = j;
			}
			for (auto [x,y]: edges){
				addedge(i,x,y);
			}
		}
	}
	
	if (crit) return;
	
	dsu(A,B);
}

int CountCritical() {
	if (crit){
		int ans=0;
		for (int i = 1; i <= m; i++){
			ans += (!fail[i]);
		}
		return ans;
	}
	
	int ans = 0;
	if (!cycles.size()) ans = n;
	else if ((int)cycles.size() == 1) ans = cycles[0];
	
  	return ans;
}

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