제출 #561758

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

rings

#include <bits/stdc++.h>
using namespace std;
int n; int ima=0, tre=0;
pair <int, int> g [1000010];
struct rijesi {
	int par [1000010];
	int dub [1000010];
	int deg [1000010];
	int c=-1, md=0, zab=-1;
	void dod (int a, int b){
		if (a==zab || b==zab || md>2) return ;
		//cout << a << " " << b << " " << zab << endl;
		deg [a]++; deg [b]++;
		md=max (md, max (deg [a], deg [b]));
		while (par [a]!=-1) a=par [a];
		while (par [b]!=-1) b=par [b];
		if (dub [b]>dub [a]) swap (a, b);
		//cout << dub [a] << " " << dub [b] << endl;
		if (a==b){
			if (c>-1) c=0;
			else c=dub [a];
		}
		else {
			dub [a]+=dub [b];
			par [b]=a;
		}
		return ;
	}
	int ans (){
		if (ima && c!=-1) return 0;
		if (md>2) return 0;
		if (c==-1) return n;
		return c; 
	}
} sol [10];
void Link (int a, int b){
	a++; b++;
	sol [0].dod (a, b);
	g [tre]={a, b};
	tre++;
	if (!ima){
		if (sol [0].md>2){
			for (int i=1; i<n+1; i++){
				if (sol [0].deg [i]>2) sol [ima=1].zab=i;
			}
			for (int i=0; i<tre; i++){
				if (g [i].first==sol [1].zab) sol [++ima].zab=g[i].second;
				if (g [i].second==sol [1].zab) sol [++ima].zab=g[i].first;
			}
			for (int i=1; i<5; i++){
				for (int j=0; j<tre; j++){
					sol [i].dod (g [j].first, g [j].second);
				}
			}
		}
	}
	else {
		for (int i=1; i<=4; i++) sol [i].dod (a, b);
	}
}
int CountCritical (){
	//cout << ima << endl;
	int x=0;
	if (ima){
		for (int i=1; i<5; i++) x+=(sol [i].ans()>0);
	}
	else x=sol [0].ans();
	return x;
}
void Init (int n){
	for (int i=0; i<5; i++){
		for (int j=1; j<n+10; j++) sol[i].dub [j]=1;
		memset (sol[i].par, -1, sizeof (sol[i].par));
	}
	/*for (int i=0; i<n; i++){
		string type; cin >> type;
		if (type=="CountCritical"){
			cout << CountCritical() << endl;
		}
		else {
			int a,b; cin >> a >> b;
			Link (a, b);
		}
	}*/
}
/*int main (){
	cin >> n;
	Init (n);
	return 0;
}*/

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