oj.uz

Submission #234616

# Submission time Handle Problem Language Result Execution time Memory
234616 2020-05-24T19:31:58 Z crossing0ver Parachute rings (IOI12_rings) C++17
37 / 100
 4000 ms 67844 KB 
#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;
bool bad[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,SZ[i] = 1;
}

bool vis[1000001];

void dfs (int v,int p,int X) {
	if (sz[v] >= 3) 
		flag = 0;
	vis[v] = 1;
	for (int i: adj[v]) {
		if (i == p || i == X) continue;
		if (vis[i]) {
			flag = 0;
		}else dfs(i,v,X);
	}
}
bool check(int v) {
	flag = 1;
	memset(vis,0,sizeof vis);
	for (int i : adj[v]) sz[i]--;
	for (int i = 0; i < n; i++)
		if (i != v && !vis[i]) dfs(i,-1,v);
	for (int i : adj[v]) sz[i]++;
	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 (center != - 1 && (A == center || B == center) ) return;
	if (more_than4.size()) center = *more_than4.begin();
	if (A == center) { ans = check(A); return;}
	if (B == center) { ans = check(B); return;} 
	int x = par(A), y = par(B);
	join(A,B);
	if (x != y && sz[A] <= 2 && sz[B] <= 2 ) 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;
		for (int j : dangerous) t += check(j);
		ans = t;
		return;
		}
	}	

	
}
int CountCritical() {
	return ans;
}

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 24960 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 20 ms 23936 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24960 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 25088 KB Output is correct
10 Correct 23 ms 25088 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 46304 KB Output is correct
2 Correct 1172 ms 59208 KB Output is correct
3 Correct 402 ms 37112 KB Output is correct
4 Correct 1195 ms 66868 KB Output is correct
5 Correct 1201 ms 66932 KB Output is correct
6 Correct 1160 ms 66168 KB Output is correct
7 Correct 398 ms 37240 KB Output is correct
8 Correct 2610 ms 65528 KB Output is correct
9 Correct 3675 ms 67844 KB Output is correct
10 Correct 891 ms 65272 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 21 ms 24960 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 20 ms 23936 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24960 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 25088 KB Output is correct
10 Correct 23 ms 25088 KB Output is correct
11 Correct 25 ms 25088 KB Output is correct
12 Correct 31 ms 25344 KB Output is correct
13 Correct 39 ms 25344 KB Output is correct
14 Execution timed out 4045 ms 25464 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 21 ms 24960 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 20 ms 23936 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24960 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 25088 KB Output is correct
10 Correct 23 ms 25088 KB Output is correct
11 Correct 25 ms 25088 KB Output is correct
12 Correct 31 ms 25344 KB Output is correct
13 Correct 39 ms 25344 KB Output is correct
14 Execution timed out 4045 ms 25464 KB Time limit exceeded
15 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 24960 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 18 ms 23936 KB Output is correct
5 Correct 20 ms 23936 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24960 KB Output is correct
8 Correct 20 ms 24064 KB Output is correct
9 Correct 22 ms 25088 KB Output is correct
10 Correct 23 ms 25088 KB Output is correct
11 Correct 486 ms 46304 KB Output is correct
12 Correct 1172 ms 59208 KB Output is correct
13 Correct 402 ms 37112 KB Output is correct
14 Correct 1195 ms 66868 KB Output is correct
15 Correct 1201 ms 66932 KB Output is correct
16 Correct 1160 ms 66168 KB Output is correct
17 Correct 398 ms 37240 KB Output is correct
18 Correct 2610 ms 65528 KB Output is correct
19 Correct 3675 ms 67844 KB Output is correct
20 Correct 891 ms 65272 KB Output is correct
21 Correct 25 ms 25088 KB Output is correct
22 Correct 31 ms 25344 KB Output is correct
23 Correct 39 ms 25344 KB Output is correct
24 Execution timed out 4045 ms 25464 KB Time limit exceeded
25 Halted 0 ms 0 KB -