Submission #69558

#	Time	Username	Problem	Language	Result	Execution time	Memory
69558		FedericoS	Parachute rings (IOI12_rings)	C++14	0 / 100	1027 ms	51340 KiB

rings

#include <vector>
#include <iostream>
using namespace std;

int N;
vector<int> grafo[1000005];
bool C[1000005];
bool V[1000005];
int A[6];
int K;
int inizio;
bool flag;
vector<int> P[6];
bool G[1000005];
bool f2;
int res;

void DFS(int k){


	for(int f:grafo[k])
		if(C[f] and !V[f]){
			V[f]=true;
			DFS(f);
		}

	int x=0;

	for(int f:grafo[k])
		if(C[f])
			x++;

	x=min(x,4);
	A[x]++;

	if(flag){
		K++;
		for(int f:grafo[k])
			if(C[f]){
				P[x].push_back(f);
			}
	}

}

void Init(int N_) {
 	N = N_;
}

void Link(int A, int B) {
	grafo[A].push_back(B);
	grafo[B].push_back(A);
}

int CountCritical() {

	fill(C,C+N,true);
	fill(V,V+N,false);
	inizio=-1;
	K=0;
	for(int i=0;i<5;i++)
		P[i].clear();
	
	for(int i=0;i<N;i++)
		if(!V[i]){
			fill(A,A+5,0);
			V[i]=true;
			DFS(i);
			if(!(A[0]==1 or (A[1]==2 and A[3]==0 and A[4]==0))){
				if(inizio==-1)
					inizio=i;
				else
					return 0;
			}
		}

	if(inizio==-1)
		return N;

	fill(C,C+N,true);
	fill(V,V+N,false);
	fill(A,A+5,0);

	flag=true;
	V[inizio]=true;
	DFS(inizio);
	flag=false;

	for(int i=0;i<N;i++)
		C[i]=V[i];

	if(A[4]>1)
		return 0;
	else if(A[4]==1){

		fill(V,V+N,false);

		C[P[4][0]]=false;
		f2=true;

		for(int i=0;i<N;i++)
			if(C[i] and !V[i]){
				fill(A,A+5,0);
				V[i]=true;
				DFS(i);
				if(!(A[0]==1 or (A[1]==2 and A[3]==0 and A[4]==0)))
					f2=false;
			}

		if(f2)
			return 1;
		else
			return 0;

	}

	if(A[3]==0)
		return K;
	else if(A[3]>4)
		return 0;

	res=0;

	fill(G,G+N,false);

	for(int i:P[3]){
		G[i]=true;
		for(int f:grafo[i])
			G[f]=true;
	}

	for(int p=0;p<N;p++)
		if(G[p]){

			fill(V,V+N,false);

			C[p]=false;
			f2=true;

			for(int i=0;i<N;i++)
				if(C[i] and !V[i]){
					fill(A,A+5,0);
					V[i]=true;
					DFS(i);
					if(!(A[0]==1 or (A[1]==2 and A[3]==0 and A[4]==0)))
						f2=false;
				}

			if(f2)
				res++;

			C[p]=true;

		}

	return res;

}

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