oj.uz

답안 #13531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13531 2015-02-23T10:12:23 Z ainta 낙하산 고리들 (IOI12_rings) C++
0 / 100
 524 ms 44548 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]){
		if (cyc == 2)Res = 0;
		return Res;
	}
	int i, r = 0;
	for (i = 1; i <= 4; i++)if (!chk[i])r++;
	return r;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Incorrect 3 ms 824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 317 ms 12780 KB Output is correct
2 Incorrect 524 ms 44548 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Incorrect 3 ms 824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Incorrect 3 ms 824 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 756 KB Output is correct
3 Incorrect 3 ms 824 KB Output isn't correct
4 Halted 0 ms 0 KB -