제출 #382389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382389		alishahali1382	낙하산 고리들 (IOI12_rings)	C++14	0 / 100	1587 ms	63124 KiB

rings

#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=1000000000000001000LL;
const int mod=1000000007;
const int MAXN=1000010, LOG=20;

int n, m, k, u, v, x, y, t, a, b;
int tree=1, deg3, ans0, cycle;
int A[MAXN], B[MAXN], deg[MAXN];
vector<int> G[MAXN], V;

struct DSU{
	int par[MAXN];
	DSU(){
		iota(par, par+MAXN, 0);
	}
	int get(int x){ return (par[x]==x?x:par[x]=get(par[x]));}
	int join(int x, int y){
		x=get(x);
		y=get(y);
		par[x]=y;
		return x!=y;
	}
} dsu;
struct Solver{
	int deg[MAXN], root, ok=1;
	DSU dsu;
	void add_edge(int u, int v){
		if (u==root || v==root) return ;
		ok&=dsu.join(u, v);
		ok&=(2>=++deg[u]);
		ok&=(2>=++deg[v]);
	}
	int Get(){ return ok;}
} solver[4];


void Init(int nn){
	n=nn;
}
void Link(int u, int v){
	if (ans0) return ;
	if (deg3){
		for (int i:{0, 1, 2, 3}) solver[i].add_edge(u, v);
		return ;
	}
	A[m]=u;
	B[m]=v;
	m++;
	deg[u]++;
	deg[v]++;
	if (deg[u]==3) swap(u, v);
	if (deg[v]==3){
		V={v};
		for (int i=0; i<m; i++) if (A[i]==v || B[i]==v) V.pb(v^A[i]^B[i]);
		for (int i:{0, 1, 2, 3}){
			solver[i].root=V[i];
			for (int j=0; j<m; j++) solver[i].add_edge(A[j], B[j]);
		}
		deg3=1;
		return ;
	}
	if (dsu.join(u, v)) return ;
	if (tree) tree=0;
	else ans0=1;
}
int CountCritical(){
	if (ans0) return 0;
	if (deg3){
		int res=0;
		for (int i:{0, 1, 2, 3}) res+=solver[i].Get();
		return res;
	}
	if (tree) return n;
	int res=0;
	for (int i=0; i<n; i++) if (dsu.get(i)==dsu.get(cycle)) res++;
	return res;
}

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