Submission #62436

#	Time	Username	Problem	Language	Result	Execution time	Memory
62436		zadrga	Parachute rings (IOI12_rings)	C++14	55 / 100	4027 ms	108080 KiB

rings

// 14.47
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF (1LL << 55)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 1000111
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
 
int n, cnt;
int deg[maxn], dep[maxn];
bool edge[maxn], found;
 
vector<int> cycles;
vector<pii> adj[maxn];
 
void Init(int N) {
	n = N;
	for(int i = 0; i < maxn; i++){
		deg[i] = 0;
		adj[i].clear();
	}
}
 
void Link(int A, int B){
	deg[A]++;
	deg[B]++;
	adj[A].pb(mp(B, ++cnt));
	adj[B].pb(mp(A, cnt));
 
//	cout << "ok link" << endl; 
}
 
void DFS(int x, int p){
	if(found)
		return;
 
	for(pii v : adj[x]){
		if(found || v.fi == p || edge[v.se])
			continue;	
 
		if(dep[v.fi]){
			cycles.pb(dep[x] - dep[v.fi] + 1);
			found = 1;
		}
 
		if(!dep[v.fi]){
			dep[v.fi] = dep[x] + 1;
			DFS(v.fi, x);
		}
	}
}
 
void checkCycles(){
	cycles.clear();
	memset(dep, 0, sizeof(dep));
 
	for(int i = 0; i < n; i++){
		if(cycles.size() >= 2)
			return;
 
		if(!dep[i]){
			found = 0;
			dep[i] = 1;
			DFS(i, -1);
		}
	}
}
 
bool check(int x){
	for(pii v : adj[x]){
		edge[v.se] = 1;
		deg[v.fi]--;
	}
 
	bool ret = 1;
	for(int i = 0; i < n; i++){
		if(i != x && deg[i] > 2){
			ret = 0;
			break;
		}
	}
 
	if(ret)
		checkCycles();
 
	ret &= (cycles.size() == 0);
 
	for(pii v : adj[x]){
		edge[v.se] = 0;
		deg[v.fi]++;
	}
 
	return ret;
}
 
int CountCritical(){
 
//	cout << "ok count" << endl; 
 
	int sz[5], v[5];
	memset(sz, 0, sizeof(sz));
	
	int max_degree = 0;
	for(int i = 0; i < n; i++){
		int cur = min(deg[i], 4);
		max_degree = max(max_degree, cur);
		v[cur] = i;
		sz[cur]++;
	}
 
	if(max_degree <= 1)
		return n;
 
	if(max_degree == 2){
		checkCycles();
		if(cycles.size() > 1)
			return 0;
 
		if(cycles.size() == 1)
			return cycles[0];
 
		return n;
	}
 
	if(max_degree == 3){
		int ans = check(v[3]);
		for(pii x : adj[v[3]])
			ans += check(x.fi);
 
		return ans;
	}
 
	if(max_degree == 4){
		if(sz[4] > 1)
			return 0;
 
		int ans = check(v[4]);
		return ans;
	}
}

Compilation message (stderr)

rings.cpp: In function 'int CountCritical()':
rings.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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