Submission #382339

#	Time	Username	Problem	Language	Result	Execution time	Memory
382339		alireza_kaviani	Parachute rings (IOI12_rings)	C++11	100 / 100	2154 ms	135056 KiB

rings

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define X			first
#define Y			second

const int MAXN = 1e6 + 10;

int n , flag , invalid[5] , cycle[5] , root[5] , sz[5][MAXN] , par[5][MAXN] , deg[5][MAXN];
vector<int> adj[MAXN];
vector<pii> E;

void Init(int N_) {
	n = N_;
	for(int i = 0 ; i < 5 ; i++){
		fill(par[i] , par[i] + MAXN , -1);
		fill(sz[i] , sz[i] + MAXN , 1);
		root[i] = -1;
	}
	root[0] = 0;
}

int Find(int ind , int v){
	return (par[ind][v] == -1 ? v : par[ind][v] = Find(ind , par[ind][v]));
}

void Union(int ind , int v , int u){
	v = Find(ind , v); u = Find(ind , u);
	if(v == u)	return;
	if(sz[ind][v] < sz[ind][u])	swap(v , u);
	par[ind][u] = v;
	sz[ind][v] += sz[ind][u];
}

void add(int ind , int v , int u){
	if(root[ind] == -1)	return;
	if(v == root[ind] || u == root[ind])	return;
	deg[ind][v]++; deg[ind][u]++;
	if(deg[ind][v] >= 3 || deg[ind][u] >= 3)	invalid[ind] = 1;
	if(Find(ind , v) == Find(ind , u)){
		if(cycle[ind] != 0)	cycle[ind] = -1;
		else	cycle[ind] = sz[ind][Find(ind , v)];
	}
	else	Union(ind , v , u);
}

void Link(int A, int B) {
	A++; B++;
	E.push_back({A , B});
	adj[A].push_back(B);
	adj[B].push_back(A);
	for(int i = 0 ; i < 5 ; i++)	add(i , A , B);
	if(flag)	return;
	if(deg[0][A] < deg[0][B])	swap(A , B);
	if(deg[0][A] >= 3){
		flag = 1;
		root[1] = A; root[2] = adj[A][0];
		root[3] = adj[A][1]; root[4] = adj[A][2];
		for(pii i : E){
			for(int j = 1 ; j < 5 ; j++)	add(j , i.X , i.Y);
		}
	}
}

int CountCritical() {
	if(invalid[0] == 0){
		if(cycle[0] == 0)	return n;
		if(cycle[0] > 0)	return cycle[0];
	}
	int ans = 0;
	for(int i = 0 ; i < 5 ; i++){
		if(root[i] != -1 && invalid[i] == 0 && cycle[i] == 0)	ans++;
	}
	return ans;
}

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