oj.uz

Submission #13530

# Submission time Handle Problem Language Result Execution time Memory
13530 2015-02-23T10:10:14 Z ainta Parachute rings (IOI12_rings) C++
0 / 100
 513 ms 44388 KB 
int n, cyc, Res;
int E[1010000][3], deg[5][1010000], chk[5], Num[5];
int par[5][1010000], SZ[1010000];
void Init(int N_) {
	n = N_;
	Res = n;
	int i;
	for (i = 1; i <= n; i++)SZ[i] = 1, par[0][i] = i;
}

int Find(int ck, int a){
	if (par[ck][a] == a)return a;
	return par[ck][a] = Find(ck, par[ck][a]);
}

void Add(int ck, int a, int b){
	if (chk[ck])return;
	if (!ck){
		E[a][deg[0][a]] = b, E[b][deg[0][b]] = a;
	}
	deg[ck][a]++, deg[ck][b]++;
	if (ck && (deg[ck][a] >= 3 || deg[ck][b] >= 3)){
		chk[ck] = 1;
		return;
	}
	a = Find(ck, a), b = Find(ck, b);
	if (a == b){
		if (!ck){
			cyc++;
			if (cyc == 1)Res = SZ[a];
		}
		else chk[ck] = 1;
	}
	else{
		par[ck][a] = b;
		if (!ck){
			SZ[b] += SZ[a];
			SZ[a] = 0;
		}
	}
}

void Make(int a){
	int i, j, k, x;
	Num[1] = a;
	for (i = 0; i < 3; i++){
		Num[2 + i] = E[a][i];
	}
	chk[0] = 1;
	for (k = 1; k <= 4; k++){
		for (i = 1; i <= n; i++)par[k][i] = i;
		for (i = 1; i <= n; i++){
			for (j = 0; j < deg[0][i]; j++){
				x = E[i][j];
				if (i == Num[k] || x == Num[k] || x > i)continue;
				Add(k, i, x);
			}
		}
	}
}

void Link(int A, int B) {
	if (!Res)return;
	A++, B++;
	if (!chk[0]){
		if (cyc == 2)Res = 0;
		Add(0, A, B);
		if (deg[0][A] == 3){
			Make(A);
		}
		else if (deg[0][B] == 3){
			Make(B);
		}
	}
	else{
		int i;
		for (i = 1; i <= 4; i++)Add(i, A, B);
	}
}

int CountCritical() {
	if (!chk[0])return Res;
	int i, r = 0;
	for (i = 1; i <= 4; i++)if (!chk[i])r++;
	return r;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 628 KB Output is correct
3 Incorrect 3 ms 792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 12724 KB Output is correct
2 Incorrect 513 ms 44388 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 628 KB Output is correct
3 Incorrect 3 ms 792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 628 KB Output is correct
3 Incorrect 3 ms 792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 628 KB Output is correct
3 Incorrect 3 ms 792 KB Output isn't correct
4 Halted 0 ms 0 KB -