제출 #234609

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234609		crossing0ver	낙하산 고리들 (IOI12_rings)	C++17	0 / 100	2481 ms	67232 KiB

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;
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]++;
	if (sz[A] == 3) {dangerous.push_back(A);for (int i:adj[A]) dangerous.push_back(i);}
	if (sz[B] == 3) {	dangerous.push_back(B);for (int i:adj[B]) dangerous.push_back(i); }
	adj[A].push_back(B);
	adj[B].push_back(A);
	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
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31