제출 #234603

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234603		crossing0ver	Parachute rings (IOI12_rings)	C++17	0 / 100	174 ms	27904 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 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) {
	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.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;
}

컴파일 시 표준 에러 (stderr) 메시지

rings.cpp: In function 'bool check(int)':
rings.cpp:44:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (int i = 0; i < n; i++)
  ^~~
rings.cpp:46:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i : adj[v]) sz[i]++;
   ^~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 17
• Subtask 3: 0 / 18
• Subtask 4: 0 / 14
• Subtask 5: 0 / 31