oj.uz

Submission #234620

# Submission time Handle Problem Language Result Execution time Memory
234620 2020-05-24T19:40:24 Z crossing0ver Parachute rings (IOI12_rings) C++17
20 / 100
 2696 ms 70776 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,help,seen[1000001];
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;
}

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) {
	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]++;
	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;
	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] == 1 || sz[B] == 1) return;
	if (sz[A]>= 3 || sz[B] >= 3) {
		int t = 0;
		for (int j : dangerous) t += check(j);
		ans = t;
		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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 20 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 20 ms 23936 KB Output is correct
6 Correct 20 ms 24064 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 24064 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 46424 KB Output is correct
2 Correct 993 ms 61408 KB Output is correct
3 Correct 371 ms 40312 KB Output is correct
4 Correct 1215 ms 67040 KB Output is correct
5 Correct 1202 ms 67012 KB Output is correct
6 Correct 1162 ms 65880 KB Output is correct
7 Correct 349 ms 41212 KB Output is correct
8 Correct 2696 ms 67832 KB Output is correct
9 Incorrect 2136 ms 70776 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 20 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 20 ms 23936 KB Output is correct
6 Correct 20 ms 24064 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 24064 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct
11 Correct 26 ms 24064 KB Output is correct
12 Incorrect 27 ms 24320 KB Output isn't correct
13 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 20 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 20 ms 23936 KB Output is correct
6 Correct 20 ms 24064 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 24064 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct
11 Correct 26 ms 24064 KB Output is correct
12 Incorrect 27 ms 24320 KB Output isn't correct
13 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 20 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 20 ms 23936 KB Output is correct
6 Correct 20 ms 24064 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 24064 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct
11 Correct 485 ms 46424 KB Output is correct
12 Correct 993 ms 61408 KB Output is correct
13 Correct 371 ms 40312 KB Output is correct
14 Correct 1215 ms 67040 KB Output is correct
15 Correct 1202 ms 67012 KB Output is correct
16 Correct 1162 ms 65880 KB Output is correct
17 Correct 349 ms 41212 KB Output is correct
18 Correct 2696 ms 67832 KB Output is correct
19 Incorrect 2136 ms 70776 KB Output isn't correct
20 Halted 0 ms 0 KB -