oj.uz

Submission #64055

# Submission time Handle Problem Language Result Execution time Memory
64055 2018-08-03T09:03:44 Z chpipis Parachute rings (IOI12_rings) C++11
37 / 100
 3436 ms 76156 KB 
#ifndef EVAL
#include "grader.h"
#endif
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MAXN = 1e6 + 5;

vector<int> gr[MAXN];
int deg[MAXN], neig3[MAXN];
int p[MAXN], sz[MAXN];
int n, numcc, total, curcycle;
int great_node;
map<int, int> cnt;
set<int> three;
bool visit[MAXN];

void Init(int _n) {
	n = _n;
	for (int i = 0; i < n; i++) {
		deg[i] = 0;
		p[i] = -1;
		sz[i] = 1;
		gr[i].clear();
	}
	numcc = n;
	total = n;
	cnt.clear();
	cnt[0] = n;
}

int fin(int x) {
	return (p[x] == -1 ? x : p[x] = fin(p[x]));
}

inline void chval(int x, int add) {
	if (deg[x] == 3)
		three.erase(x);
	cnt[deg[x]]--;
	if (cnt[deg[x]] == 0)
		cnt.erase(deg[x]);
	deg[x] += add;
	cnt[deg[x]]++;
	if (deg[x] == 3)
		three.insert(x);
}

void dfs(int u) {
	visit[u] = true;
	for (auto v : gr[u]) {
		if (visit[v]) continue;
		dfs(v);
	}
}

bool check(int w) {
	for (auto v : gr[w])
		chval(v, -1);
	memset(visit, false, sizeof visit);
	visit[w] = true;
	int comps = cnt[0] + cnt[1] / 2;
	int want = 0;
	for (int u = 0; u < n; u++) {
		if (!visit[u]) {
			want++;
			dfs(u);
		}
	}
	for (auto v : gr[w])
		chval(v, +1);
	return want == comps;
}

void Link(int a, int b) {
	if (deg[a] == 3) {
		for (auto v : gr[a])
			neig3[v]--;
	}
	if (deg[b] == 3) {
		for (auto v : gr[b])
			neig3[v]--;
	}
	chval(a, +1);
	chval(b, +1);
	gr[a].pb(b);
	gr[b].pb(a);
	if (deg[a] == 3) {
		for (auto v : gr[a])
			neig3[v]++;
	}
	if (deg[b] == 3) {
		for (auto v : gr[b])
			neig3[v]++;
	}
	if (deg[a] > 3) {
		great_node = a;
	} else if (deg[b] > 3) {
		great_node = b;
	}
	int ra = fin(a), rb = fin(b);
	if (ra != rb) {
		numcc--;
		if (sz[ra] > sz[rb]) {
			p[rb] = ra;
			sz[ra] += sz[rb];
		} else {
			p[ra] = rb;
			sz[rb] += sz[ra];
		}
	} else {
		curcycle = sz[ra];
		if (!three.empty() && fin(*three.begin()) != ra) {
			total = 0;
			return;
		}
	}
	int big = 0;
	for (auto it = cnt.rbegin(); it != cnt.rend(); it++) {
		if (it->first <= 3) break;
		big += it->second;
		if (big > 1) break;
	}
	if (big == 0 && cnt[3] == 0) {
		// everything is either a chain or a cycle
		int comps = cnt[0] + cnt[1] / 2;
		if (comps == numcc) {
			// every component is a chain
			total = n;
		} else if (comps == numcc - 1) {
			total = curcycle;
		} else {
			total = 0;
		}
	} else if (big > 1 || cnt[3] > 4) {
		total = 0;
	} else if (big == 1) {
		if (neig3[great_node] != (int)three.size()) {
			total = 0;
		} else {
			bool found = (great_node == a || great_node == b);
			for (auto v : gr[a])
				if (v == great_node)
					found = true;
			for (auto v : gr[b])
				if (v == great_node)
					found = true;
			if (found) {
				if (check(great_node)) {
					total = 1;
				} else {
					total = 0;
				}
			}
		}
	} else {
		// now big = 0 and cnt[3] > 0
		const int c = (int)three.size();
		set<int> proc;
		for (auto u : three) {
			proc.insert(u);
			for (auto v : gr[u])
				proc.insert(v);
		}
		bool found = false;
		for (auto it : proc) {
			if (it == a || it == b)
				found = true;
		}
		if (!found) return;
		total = 0;
		for (auto u : proc) {
			if (deg[u] == 3 && neig3[u] == c - 1) {
				if (check(u))
					total++;
			} else if (deg[u] < 3 && neig3[u] == c) {
				if (check(u))
					total++;
			}
		}
	}
}

int CountCritical() {
	return total;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 28 ms 25212 KB Output is correct
3 Correct 31 ms 25248 KB Output is correct
4 Correct 22 ms 25248 KB Output is correct
5 Correct 24 ms 25248 KB Output is correct
6 Correct 24 ms 25248 KB Output is correct
7 Correct 25 ms 25248 KB Output is correct
8 Correct 25 ms 25248 KB Output is correct
9 Correct 31 ms 25364 KB Output is correct
10 Correct 34 ms 25364 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 46796 KB Output is correct
2 Correct 3436 ms 59588 KB Output is correct
3 Correct 2159 ms 76156 KB Output is correct
4 Correct 1435 ms 76156 KB Output is correct
5 Correct 1428 ms 76156 KB Output is correct
6 Correct 1448 ms 76156 KB Output is correct
7 Correct 1840 ms 76156 KB Output is correct
8 Correct 3349 ms 76156 KB Output is correct
9 Correct 2842 ms 76156 KB Output is correct
10 Correct 995 ms 76156 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 28 ms 25212 KB Output is correct
3 Correct 31 ms 25248 KB Output is correct
4 Correct 22 ms 25248 KB Output is correct
5 Correct 24 ms 25248 KB Output is correct
6 Correct 24 ms 25248 KB Output is correct
7 Correct 25 ms 25248 KB Output is correct
8 Correct 25 ms 25248 KB Output is correct
9 Correct 31 ms 25364 KB Output is correct
10 Correct 34 ms 25364 KB Output is correct
11 Incorrect 29 ms 76156 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 28 ms 25212 KB Output is correct
3 Correct 31 ms 25248 KB Output is correct
4 Correct 22 ms 25248 KB Output is correct
5 Correct 24 ms 25248 KB Output is correct
6 Correct 24 ms 25248 KB Output is correct
7 Correct 25 ms 25248 KB Output is correct
8 Correct 25 ms 25248 KB Output is correct
9 Correct 31 ms 25364 KB Output is correct
10 Correct 34 ms 25364 KB Output is correct
11 Incorrect 29 ms 76156 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 28 ms 25212 KB Output is correct
3 Correct 31 ms 25248 KB Output is correct
4 Correct 22 ms 25248 KB Output is correct
5 Correct 24 ms 25248 KB Output is correct
6 Correct 24 ms 25248 KB Output is correct
7 Correct 25 ms 25248 KB Output is correct
8 Correct 25 ms 25248 KB Output is correct
9 Correct 31 ms 25364 KB Output is correct
10 Correct 34 ms 25364 KB Output is correct
11 Correct 545 ms 46796 KB Output is correct
12 Correct 3436 ms 59588 KB Output is correct
13 Correct 2159 ms 76156 KB Output is correct
14 Correct 1435 ms 76156 KB Output is correct
15 Correct 1428 ms 76156 KB Output is correct
16 Correct 1448 ms 76156 KB Output is correct
17 Correct 1840 ms 76156 KB Output is correct
18 Correct 3349 ms 76156 KB Output is correct
19 Correct 2842 ms 76156 KB Output is correct
20 Correct 995 ms 76156 KB Output is correct
21 Incorrect 29 ms 76156 KB Output isn't correct
22 Halted 0 ms 0 KB -