oj.uz

Submission #62428

# Submission time Handle Problem Language Result Execution time Memory
62428 2018-07-28T12:50:03 Z zadrga Parachute rings (IOI12_rings) C++14
0 / 100
 785 ms 53132 KB 
// 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;
	}

	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];
	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

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

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31608 KB Output is correct
2 Incorrect 30 ms 31608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 544 ms 48256 KB Output is correct
2 Incorrect 785 ms 53132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31608 KB Output is correct
2 Incorrect 30 ms 31608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31608 KB Output is correct
2 Incorrect 30 ms 31608 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 31608 KB Output is correct
2 Incorrect 30 ms 31608 KB Output isn't correct
3 Halted 0 ms 0 KB -