oj.uz

답안 #559850

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559850 2022-05-10T18:13:42 Z drkarlicio2107 낙하산 고리들 (IOI12_rings) C++14
0 / 100
 149 ms 18740 KB 
#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]!=0) a=par [a];
		while (par [b]!=0) 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;
	}
	/*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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 18740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -