Submission #119216

#	Time	Username	Problem	Language	Result	Execution time	Memory
119216		ioilolcom	Parachute rings (IOI12_rings)	C++14	0 / 100	4086 ms	98768 KiB

rings

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
int N;
vector<int> edges;
const int M=1e6+7;
set<int> adj[M];
int deg[M];
void Init(int N_) {
	N = N_;
}

void Link(int A, int B) {
	adj[A].insert(B);
	adj[B].insert(A);
	deg[A]++;
	deg[B]++;
}
vector<char> color;
bool dfs(int v) {
	color[v] = 1;
	for (int u : adj[v]) {
		if (color[u] == 0) {
			if (dfs(u))
				return true;
		} else if (color[u] == 1) {
			return true;
		}
	}
	color[v] = 2;
	return false;
}

bool cycle() {
	color.assign(N,-1);
	for(int x=0; x<N; x++) {
		if(color[x]) {
			continue;
		}
		if(dfs(x)) {
			return 1;
		}
	}
	return 0;
}

int CountCritical() {
	int ans=0;
	for(int i=0; i<N; i++) {
		vector<int> lol;
		int tmp=deg[i];
		int cnt=0;
		deg[i]=0;
		for(int j=0; j<N; j++) {
			if(adj[i].count(j)) {
				lol.push_back(j);
				adj[j].erase(i);
				adj[i].erase(j);
				deg[j]--;
			}
			if(deg[j]>=3) {
				cnt++;
			}
		}
		deg[i]=tmp;
		for(int v:lol) {
			adj[i].insert(v);
			adj[v].insert(i);
			deg[v]++;
		}
		ans+=((!cnt)&&!cycle());
	}
	return ans;
}

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