oj.uz

답안 #62433

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62433 2018-07-28T12:59:02 Z zadrga 낙하산 고리들 (IOI12_rings) C++14
0 / 100
 2045 ms 92948 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, 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]]++;
	}

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

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

	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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 31608 KB Output is correct
2 Correct 34 ms 31880 KB Output is correct
3 Correct 33 ms 31904 KB Output is correct
4 Correct 31 ms 31904 KB Output is correct
5 Correct 34 ms 31944 KB Output is correct
6 Correct 37 ms 32188 KB Output is correct
7 Correct 32 ms 32188 KB Output is correct
8 Correct 32 ms 32188 KB Output is correct
9 Incorrect 44 ms 32188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 48352 KB Output is correct
2 Correct 971 ms 57208 KB Output is correct
3 Correct 934 ms 61280 KB Output is correct
4 Correct 1289 ms 63852 KB Output is correct
5 Correct 1316 ms 64456 KB Output is correct
6 Correct 1373 ms 92948 KB Output is correct
7 Correct 958 ms 92948 KB Output is correct
8 Incorrect 2045 ms 92948 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 31608 KB Output is correct
2 Correct 34 ms 31880 KB Output is correct
3 Correct 33 ms 31904 KB Output is correct
4 Correct 31 ms 31904 KB Output is correct
5 Correct 34 ms 31944 KB Output is correct
6 Correct 37 ms 32188 KB Output is correct
7 Correct 32 ms 32188 KB Output is correct
8 Correct 32 ms 32188 KB Output is correct
9 Incorrect 44 ms 32188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 31608 KB Output is correct
2 Correct 34 ms 31880 KB Output is correct
3 Correct 33 ms 31904 KB Output is correct
4 Correct 31 ms 31904 KB Output is correct
5 Correct 34 ms 31944 KB Output is correct
6 Correct 37 ms 32188 KB Output is correct
7 Correct 32 ms 32188 KB Output is correct
8 Correct 32 ms 32188 KB Output is correct
9 Incorrect 44 ms 32188 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 31608 KB Output is correct
2 Correct 34 ms 31880 KB Output is correct
3 Correct 33 ms 31904 KB Output is correct
4 Correct 31 ms 31904 KB Output is correct
5 Correct 34 ms 31944 KB Output is correct
6 Correct 37 ms 32188 KB Output is correct
7 Correct 32 ms 32188 KB Output is correct
8 Correct 32 ms 32188 KB Output is correct
9 Incorrect 44 ms 32188 KB Output isn't correct
10 Halted 0 ms 0 KB -