oj.uz

Submission #234601

# Submission time Handle Problem Language Result Execution time Memory
234601 2020-05-24T19:00:19 Z crossing0ver Parachute rings (IOI12_rings) C++17
0 / 100
 188 ms 28032 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 a = par(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) {
	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 = 0; i < n; i++)
		if (i != v && !vis[i]) dfs(i,-1,v);
	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.erase(A),more_than4.insert(A);
	if (sz[A] >= 4) more_than4.erase(B),more_than4.insert(B);
	if (more_than4.size() >= 2) { ans = 0; return; }
	if (center != - 1 && (A == center || B == center) ) return;
	if (center != -1 && A != center && B != center) { ans = 0; return;}
	if (more_than4.size()) center = *more_than4.begin();
	if (A == center) { check(A); return;}
	if (B == center) { 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 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 28032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -