Submission #595927

#	Time	Username	Problem	Language	Result	Execution time	Memory
595927		fuad27	Parachute rings (IOI12_rings)	C++17	20 / 100	4046 ms	200420 KiB

rings

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n;
vector<int> g[N];
vector<vector<int>> v(N, vector<int> (N,0));
void Init(int N_) {
	n = N_;
}

void Link(int A, int B) {
	if(v[A][B])return;
	g[A].push_back(B);
	g[B].push_back(A);
	v[A][B]=1;
	v[B][A]=1;
}
int cur;
bool check;
bool vis[N];
void dfs(int at, int p) {
	if(vis[at])return;
	vis[at]=1;
	int cnt=0;
	for(int to:g[at]) {
		if(to == p or to == cur)continue;
		if(vis[to]){
			check=false;
			return;
		}
		dfs(to,at);
		cnt++;
	}
	if(cnt>1)check=false;
}
int CountCritical() {
	// cout<<"$$$$"<<endl;
	int ans=0;
	for(int j = 0;j<n;j++) {
		cur=j;
		check=1;
		for(int i = 0;i<n;i++)vis[i]=0;
		for(int i = 0;i<n;i++) {
			if(i == j)continue;
			int deg=0;
			for(int j:g[i]) {
				if(j!=cur)deg++;
			}
			if(deg<=1 and !vis[i]){
				dfs(i,-1);
			}
		}
		for(int i = 0;i<n;i++) {
			if(i==cur)continue;
			if(!vis[i]){
				check=false;
				// cout<<i<<" ";
			}
		}
		ans+=check;
	}
	return ans;
}

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