제출 #63108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63108		reality	낙하산 고리들 (IOI12_rings)	C++17	100 / 100	837 ms	52400 KiB

rings

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

const int NN = 2e6 + 5;

int n;

int f[NN];

int deg[NN];

int sz[NN];

vector < pii > e;

int ans;

int gg[5][NN];

int dg[5][NN];

vi who;

vi ANS;

int szz;

int cyc;

int g(int w,int k) {
	return gg[w][k] == k ? k : gg[w][k] = g(w,gg[w][k]);
}

int get(int k) {
	return k == f[k] ? k : f[k] = get(f[k]);
}

void Init(int N_) {
  	n = N_;
  	ans = n;
  	for (int i = 1;i <= n;++i) {
  		f[i] = i,sz[i] = 1;
  	}
}



void Link(int A, int B) {
	++A;++B;
	e.pb(mp(A,B));
	if (!szz && (deg[A] >= 2 || deg[B] >= 2)) {
		if (deg[A] < 2)
			swap(A,B);
		for (auto it : e) {
			if (it.fi == A)
				who.pb(it.se);
			else
			if (it.se == A)
				who.pb(it.fi);
		}
		who.pb(A);
		szz = who.size();
		ANS = vi(szz,1);
		for (int i = 0;i < szz;++i) {
			for (int j = 1;j <= n;++j)
				gg[i][j] = j,dg[i][j] = 0;
			for (auto it : e) {
				if (!ANS[i])
					break;
				if (it.fi == who[i] || it.se == who[i])
					continue;
				int x = g(i,it.fi);
				int y = g(i,it.se);
				++dg[i][it.fi];
				++dg[i][it.se];
				ANS[i] &= dg[i][it.fi] <= 2 && dg[i][it.se] <= 2 && x != y;
				gg[i][x] = y;
			}
		}
	} else
	if (szz) {
		for (int i = 0;i < szz;++i) {
			if (A == who[i] || B == who[i] || !ANS[i])
				continue;
			int x = g(i,A);
			int y = g(i,B);
			++dg[i][A];
			++dg[i][B];
			ANS[i] &= dg[i][A] <= 2 && dg[i][B] <= 2 && x != y;
			gg[i][x] = y;
		}
	} else 
	if (cyc <= 1) {
		int x = get(A);
		int y = get(B);
		++deg[A];
		++deg[B];
		if (x == y)
			++cyc,ans = (cyc == 1) * sz[x];
		else {
			sz[y] += sz[x];
			sz[x] = 0;
			f[x] = y;
		}
	}

}

int CountCritical() {
	if (szz)
		return accumulate(all(ANS),0);
	return ans;
}

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