oj.uz

Submission #234607

# Submission time Handle Problem Language Result Execution time Memory
234607 2020-05-24T19:09:25 Z crossing0ver Parachute rings (IOI12_rings) C++17
0 / 100
 1828 ms 81068 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;
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 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) dangerous.push_back(A);
	if (sz[B] == 3) dangerous.push_back(B);
	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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 21 ms 25088 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24832 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 21 ms 25088 KB Output is correct
10 Incorrect 22 ms 25088 KB Output isn't correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 46584 KB Output is correct
2 Correct 1068 ms 70024 KB Output is correct
3 Correct 353 ms 49656 KB Output is correct
4 Correct 1225 ms 80380 KB Output is correct
5 Correct 1224 ms 80504 KB Output is correct
6 Correct 1184 ms 78840 KB Output is correct
7 Correct 350 ms 49272 KB Output is correct
8 Correct 1587 ms 77688 KB Output is correct
9 Incorrect 1828 ms 81068 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 21 ms 25088 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24832 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 21 ms 25088 KB Output is correct
10 Incorrect 22 ms 25088 KB Output isn't 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 25088 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24832 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 21 ms 25088 KB Output is correct
10 Incorrect 22 ms 25088 KB Output isn't correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 21 ms 25088 KB Output is correct
3 Correct 21 ms 25088 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 20 ms 24064 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 20 ms 24832 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 21 ms 25088 KB Output is correct
10 Incorrect 22 ms 25088 KB Output isn't correct