Submission #234624

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
234624	2020-05-24T19:52:13 Z	crossing0ver	Parachute rings (IOI12_rings)	C++17	55 / 100	4000 ms	71708 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],change;
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]) 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) {change = 1;add(A);for (int i:adj[A]) add(i);}
	if (sz[B] == 3) {change = 1;add(B);for (int i : adj[B]) add(i);}
	if (sz[A] >= 4) more_than4.insert(A),change = 1;
	if (sz[B] >= 4) more_than4.insert(B),change = 1;
	if (more_than4.size() >= 2) { ans = 0; return; }
	if (A == center || B == center ) { change = 0; 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) {
		if (center != -1 ) {
			ans = check(center);
			return;
		}
		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

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	21 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	19 ms	23936 KB	Output is correct
6	Correct	20 ms	23936 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	21 ms	24064 KB	Output is correct
9	Correct	21 ms	24064 KB	Output is correct
10	Correct	22 ms	24096 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	461 ms	46840 KB	Output is correct
2	Correct	1220 ms	62328 KB	Output is correct
3	Correct	396 ms	40952 KB	Output is correct
4	Correct	1191 ms	67960 KB	Output is correct
5	Correct	1199 ms	68068 KB	Output is correct
6	Correct	1156 ms	66936 KB	Output is correct
7	Correct	391 ms	41080 KB	Output is correct
8	Correct	2681 ms	68908 KB	Output is correct
9	Correct	3763 ms	71708 KB	Output is correct
10	Correct	876 ms	66132 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	21 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	19 ms	23936 KB	Output is correct
6	Correct	20 ms	23936 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	21 ms	24064 KB	Output is correct
9	Correct	21 ms	24064 KB	Output is correct
10	Correct	22 ms	24096 KB	Output is correct
11	Correct	23 ms	24192 KB	Output is correct
12	Correct	28 ms	24320 KB	Output is correct
13	Correct	28 ms	24320 KB	Output is correct
14	Correct	209 ms	24312 KB	Output is correct
15	Correct	311 ms	24392 KB	Output is correct
16	Correct	23 ms	24320 KB	Output is correct
17	Correct	21 ms	24064 KB	Output is correct
18	Correct	23 ms	24320 KB	Output is correct
19	Correct	23 ms	24320 KB	Output is correct
20	Correct	26 ms	24448 KB	Output is correct

Subtask #4
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	21 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	19 ms	23936 KB	Output is correct
6	Correct	20 ms	23936 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	21 ms	24064 KB	Output is correct
9	Correct	21 ms	24064 KB	Output is correct
10	Correct	22 ms	24096 KB	Output is correct
11	Correct	23 ms	24192 KB	Output is correct
12	Correct	28 ms	24320 KB	Output is correct
13	Correct	28 ms	24320 KB	Output is correct
14	Correct	209 ms	24312 KB	Output is correct
15	Correct	311 ms	24392 KB	Output is correct
16	Correct	23 ms	24320 KB	Output is correct
17	Correct	21 ms	24064 KB	Output is correct
18	Correct	23 ms	24320 KB	Output is correct
19	Correct	23 ms	24320 KB	Output is correct
20	Correct	26 ms	24448 KB	Output is correct
21	Correct	38 ms	25592 KB	Output is correct
22	Correct	50 ms	26488 KB	Output is correct
23	Correct	59 ms	27260 KB	Output is correct
24	Execution timed out	4081 ms	27416 KB	Time limit exceeded
25	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	23808 KB	Output is correct
2	Correct	21 ms	24064 KB	Output is correct
3	Correct	21 ms	24192 KB	Output is correct
4	Correct	19 ms	23936 KB	Output is correct
5	Correct	19 ms	23936 KB	Output is correct
6	Correct	20 ms	23936 KB	Output is correct
7	Correct	19 ms	23936 KB	Output is correct
8	Correct	21 ms	24064 KB	Output is correct
9	Correct	21 ms	24064 KB	Output is correct
10	Correct	22 ms	24096 KB	Output is correct
11	Correct	461 ms	46840 KB	Output is correct
12	Correct	1220 ms	62328 KB	Output is correct
13	Correct	396 ms	40952 KB	Output is correct
14	Correct	1191 ms	67960 KB	Output is correct
15	Correct	1199 ms	68068 KB	Output is correct
16	Correct	1156 ms	66936 KB	Output is correct
17	Correct	391 ms	41080 KB	Output is correct
18	Correct	2681 ms	68908 KB	Output is correct
19	Correct	3763 ms	71708 KB	Output is correct
20	Correct	876 ms	66132 KB	Output is correct
21	Correct	23 ms	24192 KB	Output is correct
22	Correct	28 ms	24320 KB	Output is correct
23	Correct	28 ms	24320 KB	Output is correct
24	Correct	209 ms	24312 KB	Output is correct
25	Correct	311 ms	24392 KB	Output is correct
26	Correct	23 ms	24320 KB	Output is correct
27	Correct	21 ms	24064 KB	Output is correct
28	Correct	23 ms	24320 KB	Output is correct
29	Correct	23 ms	24320 KB	Output is correct
30	Correct	26 ms	24448 KB	Output is correct
31	Correct	38 ms	25592 KB	Output is correct
32	Correct	50 ms	26488 KB	Output is correct
33	Correct	59 ms	27260 KB	Output is correct
34	Execution timed out	4081 ms	27416 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

Submission #234624

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