답안 #234623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234623	2020-05-24T19:46:50 Z	crossing0ver	낙하산 고리들 (IOI12_rings)	C++17	55 / 100	4000 ms	71896 KB

rings

#include<bits/stdc++.h>
using namespace std;
int n,cycle_size,cycles;
vector<int> adj[1000001];
bool flag = 1;
int sz[1000001],SZ[1000001], P[1000001] , ans, center = -1,help,seen[1000001];
bool bad[1000001],good[1000001];
set<int> more_than4;
int par(int a) {
	if (a != P[a]) 
		return P[a] = par(P[a]);
	return a;
}
void join(int a,int b) {
	int x = par(a);
	int y = par(b);
	if (x == y) return;
	if (SZ[x] > SZ[y]) swap(x,y);
	P[x] = y;
	SZ[y] += SZ[x];
}

void Init(int N) {
	ans = n = N;
	for (int i = 0 ; i < n; i++)
		P[i] = i,good[i] = SZ[i] = 1;
}

int vis[1000001];

void dfs (int v,int p,int X) {
	if (sz[v] >= 3) 
		flag = 0;
	vis[v] = help;
	for (int i: adj[v]) {
		if (i == p || i == X) continue;
		if (vis[i] == help) {
			flag = 0;
		}else dfs(i,v,X);
	}
}
bool check(int v) {
	if (good[v] == 0) return 0;
	help++;
	flag = 1;
	for (int i : adj[v]) sz[i]--;
	for (int i = 0; i < n; i++)
		if (i != v && help != vis[i]) dfs(i,-1,v);
	for (int i : adj[v]) sz[i]++;
	good[v] = flag;
	return flag; 
}
vector<int> dangerous;
void add(int x) {
	if (bad[x]) return;
	bad[x] = 1; dangerous.push_back(x);
}
void Link(int A, int B) {
	if (ans == 0) return;
	sz[A]++;
	sz[B]++;
	adj[A].push_back(B);
	adj[B].push_back(A);
	if (sz[A] == 3) {add(A);for (int i:adj[A]) add(i);}
	if (sz[B] == 3) {	add(B);for (int i : adj[B]) add(i);}
	if (sz[A] >= 4) more_than4.insert(A);
	if (sz[B] >= 4) more_than4.insert(B);
	if (more_than4.size() >= 2) { ans = 0; return; }
	if (A == center || B == center ) return;
	int x = par(A), y = par(B);
	join(A,B);
	if (x != y && sz[A] <= 2 && sz[B] <= 2 ) return;
	if (more_than4.size()) center = *more_than4.begin(); 
	if (A == center) { ans = check(A); return;}
	if (B == center) { ans = check(B); return;}
	if (sz[A]>= 3 || sz[B] >= 3) {
		int t = 0;
		for (int j : dangerous) t += check(j);
		ans = t;
		return;
	}
	if (sz[A] == 1 || sz[B] == 1) return;
	if (x == y && sz[A] == 2 && sz[B] == 2) {
		if (dangerous.empty()) {
			   cycles++;
			   cycle_size = SZ[par(A)];
			   if (cycles > 1) { ans = 0; return;}
			   ans = cycle_size;
			   return ;
		} else {
			int t = 0;
			if (center != -1 ){
				ans = check(center);
				return;
			}
		for (int j : dangerous) t += check(j);
		ans = t;
		return;
		}
	}	
}
int CountCritical() {
	return ans;
}

Compilation message

rings.cpp: In function 'void Init(int)':
rings.cpp:26:28: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   P[i] = i,good[i] = SZ[i] = 1;
                      ~~~~~~^~~

Subtask #1
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24192 KB	Output is correct
3	Correct	20 ms	24064 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	20 ms	24056 KB	Output is correct
6	Correct	20 ms	24128 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	20 ms	24064 KB	Output is correct
9	Correct	21 ms	24192 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	487 ms	46840 KB	Output is correct
2	Correct	1196 ms	62328 KB	Output is correct
3	Correct	399 ms	41080 KB	Output is correct
4	Correct	1200 ms	67916 KB	Output is correct
5	Correct	1208 ms	67916 KB	Output is correct
6	Correct	1181 ms	66808 KB	Output is correct
7	Correct	383 ms	41080 KB	Output is correct
8	Correct	2666 ms	68756 KB	Output is correct
9	Correct	3753 ms	71896 KB	Output is correct
10	Correct	855 ms	66172 KB	Output is correct

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24192 KB	Output is correct
3	Correct	20 ms	24064 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	20 ms	24056 KB	Output is correct
6	Correct	20 ms	24128 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	20 ms	24064 KB	Output is correct
9	Correct	21 ms	24192 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct
11	Correct	23 ms	24192 KB	Output is correct
12	Correct	27 ms	24448 KB	Output is correct
13	Correct	31 ms	24440 KB	Output is correct
14	Correct	824 ms	24416 KB	Output is correct
15	Correct	1039 ms	24696 KB	Output is correct
16	Correct	23 ms	24440 KB	Output is correct
17	Correct	21 ms	24192 KB	Output is correct
18	Correct	23 ms	24448 KB	Output is correct
19	Correct	23 ms	24448 KB	Output is correct
20	Correct	26 ms	24448 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24192 KB	Output is correct
3	Correct	20 ms	24064 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	20 ms	24056 KB	Output is correct
6	Correct	20 ms	24128 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	20 ms	24064 KB	Output is correct
9	Correct	21 ms	24192 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct
11	Correct	23 ms	24192 KB	Output is correct
12	Correct	27 ms	24448 KB	Output is correct
13	Correct	31 ms	24440 KB	Output is correct
14	Correct	824 ms	24416 KB	Output is correct
15	Correct	1039 ms	24696 KB	Output is correct
16	Correct	23 ms	24440 KB	Output is correct
17	Correct	21 ms	24192 KB	Output is correct
18	Correct	23 ms	24448 KB	Output is correct
19	Correct	23 ms	24448 KB	Output is correct
20	Correct	26 ms	24448 KB	Output is correct
21	Correct	38 ms	25976 KB	Output is correct
22	Correct	50 ms	27128 KB	Output is correct
23	Correct	60 ms	28024 KB	Output is correct
24	Execution timed out	4075 ms	27228 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	20 ms	24192 KB	Output is correct
3	Correct	20 ms	24064 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	20 ms	24056 KB	Output is correct
6	Correct	20 ms	24128 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	20 ms	24064 KB	Output is correct
9	Correct	21 ms	24192 KB	Output is correct
10	Correct	21 ms	24192 KB	Output is correct
11	Correct	487 ms	46840 KB	Output is correct
12	Correct	1196 ms	62328 KB	Output is correct
13	Correct	399 ms	41080 KB	Output is correct
14	Correct	1200 ms	67916 KB	Output is correct
15	Correct	1208 ms	67916 KB	Output is correct
16	Correct	1181 ms	66808 KB	Output is correct
17	Correct	383 ms	41080 KB	Output is correct
18	Correct	2666 ms	68756 KB	Output is correct
19	Correct	3753 ms	71896 KB	Output is correct
20	Correct	855 ms	66172 KB	Output is correct
21	Correct	23 ms	24192 KB	Output is correct
22	Correct	27 ms	24448 KB	Output is correct
23	Correct	31 ms	24440 KB	Output is correct
24	Correct	824 ms	24416 KB	Output is correct
25	Correct	1039 ms	24696 KB	Output is correct
26	Correct	23 ms	24440 KB	Output is correct
27	Correct	21 ms	24192 KB	Output is correct
28	Correct	23 ms	24448 KB	Output is correct
29	Correct	23 ms	24448 KB	Output is correct
30	Correct	26 ms	24448 KB	Output is correct
31	Correct	38 ms	25976 KB	Output is correct
32	Correct	50 ms	27128 KB	Output is correct
33	Correct	60 ms	28024 KB	Output is correct
34	Execution timed out	4075 ms	27228 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

답안 #234623

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 17.0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
17.0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
0 / 14.0

Subtask #5
0 / 31.0