Submission #107560

#	Time	Username	Problem	Language	Result	Execution time	Memory
107560		ekrem	Parachute rings (IOI12_rings)	C++98	100 / 100	2126 ms	117372 KiB

rings

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define N 1000005
using namespace std;

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

int n, m, k, f, ata[5][N], kom[5][N],dur[5], ne[5], son[5], say, vis[N];
ii b[N];
vector < int > g[N];

int atabul(int d, int x){return ata[d][x] = (ata[d][x] != x) ? atabul(d, ata[d][x]) : x;}

bool bir(int d, int u, int v){
	int xx = atabul(d, u);
	int yy = atabul(d, v);
	if(xx != yy){
		if(rand()%2)
			ata[d][xx] = yy;
		else
			ata[d][yy] = xx;
		return 1;
	}
	return 0;
}

void Init(int nn){

	srand(time(0));

	n = nn;
	for(int i = 1; i <= n; i++)
		for(int j = 0; j < 5; j++)
			ata[j][i] = i;

	for(int i = 1; i <= 4; i++){
		son[i] = dur[i] = 1;
	}

	dur[0] = n;
}

void dfs(int node){
	say++;
	vis[node] = 1;
	for(int i = 0; i < g[node].size(); i++)
		if(!vis[g[node][i]])
			dfs(g[node][i]);
}

void Link(int u, int v){
	u++;v++;
	kom[0][u]++;
	kom[0][v]++;

	g[u].pb(v);
	g[v].pb(u);

	b[++m] = mp(u, v);
	
	if(!f){
		if(kom[0][u] == 3){
			dur[0] = 0;
			f = 1;
			ne[++k] = u;
			for(int i = 0; i < g[u].size(); i++)
				ne[++k] = g[u][i];
		} else if(kom[0][v] == 3){
			dur[0] = 0;
			f = 1;
			ne[++k] = v;
			for(int i = 0; i < g[v].size(); i++)
				ne[++k] = g[v][i];
			// cout << "Pat" << " " << ne[1] << " " << ne[2] << " " << ne[3] << " " << ne[4] << endl;
		} else{
			if(!bir(0, u, v)){
				if(dur[0] != n)
					dur[0] = 0;
				else{
					say = 0;
					dfs(u);
					dur[0] = say;
				}
			}
		}
	}
}

int CountCritical(){
	if(!f)
		return dur[0];
	int ans = 0;
	for(int i = 1; i <= 4; i++){
		if(!dur[i])
			continue;
		for(;son[i] <= m; son[i]++){
			int u = b[son[i]].st;
			int v = b[son[i]].nd;
			if(u == ne[i] or v == ne[i])
				continue;
			// cout << i << " " << u << " " << v << endl;
			kom[i][u]++;
			kom[i][v]++;
			if(kom[i][u] == 3)
				dur[i] = 0;
			if(kom[i][v] == 3)
				dur[i] = 0;
			if(!bir(i, u, v))
				dur[i] = 0;
		}
		ans += dur[i];
	}
	return ans;
}

// int main() {
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	Init(7);
// 	cout << CountCritical() << endl;
// 	Link(1, 2);
// 	cout << CountCritical() << endl;	
// 	Link(0, 5);
// 	cout << CountCritical() << endl;	
// 	Link(2, 0);
// 	cout << CountCritical() << endl;	
// 	Link(3, 2);
// 	cout << CountCritical() << endl;	
// 	Link(3, 5);
// 	cout << CountCritical() << endl;	
// 	Link(4, 3);
// 	cout << CountCritical() << endl;	
// 	return 0;
// }

Compilation message (stderr)

rings.cpp: In function 'void dfs(int)':
rings.cpp:51:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++)
                 ~~^~~~~~~~~~~~~~~~
rings.cpp: In function 'void Link(int, int)':
rings.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < g[u].size(); i++)
                   ~~^~~~~~~~~~~~~
rings.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0; i < g[v].size(); i++)
                   ~~^~~~~~~~~~~~~

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