Submission #62434

#	Time	Username	Problem	Language	Result	Execution time	Memory
62434		zadrga	Parachute rings (IOI12_rings)	C++14	0 / 100	981 ms	57248 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, sz[5], v[5];
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;
			return;
		}

		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;
		sz[deg[v.fi]]--;
		deg[v.fi]--;
		sz[deg[v.fi]]++;
	}
	sz[deg[x]]--;

	bool ret = (sz[3] == 0 && sz[4] == 0);
	checkCycles();

	ret &= (cycles.size() == 0);

	sz[deg[x]]++;
	for(pii v : adj[x]){
		edge[v.se] = 0;
		sz[deg[v.fi]]--;
		deg[v.fi]++;
		sz[deg[v.fi]]++;
	}

	return ret;
}

int CountCritical(){

//	cout << "ok count" << endl; 
	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:147:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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