oj.uz

Submission #64084

# Submission time Handle Problem Language Result Execution time Memory
64084 2018-08-03T10:31:29 Z chpipis Parachute rings (IOI12_rings) C++11
20 / 100
 4000 ms 48556 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);
	chval(w, -(int)gr[w].size() - 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);
		}
	}
	chval(w, +(int)gr[w].size() + 1);
	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];
	}
	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 (ra == rb) {
		if (big == 1 && fin(great_node) != ra) {
			total = 0;
			return;
		} else if (big == 0 && cnt[3] > 0 && fin(*three.begin()) != ra) {
			total = 0;
			return;
		}
	}
	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 (true || found || (ra == rb)) {
				if (check(great_node)) {
					total = 1;
				} else {
					total = 0;
				}
			}
		}
	} else if (cnt[3] > 0) {
		// 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 (true || found || (ra == rb)) {
			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++;
				}
			}
		}
		/* else {
			if (ra != rb || total == 0) 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 23 ms 23804 KB Output is correct
2 Correct 959 ms 25340 KB Output is correct
3 Correct 669 ms 25340 KB Output is correct
4 Correct 22 ms 25340 KB Output is correct
5 Correct 27 ms 25340 KB Output is correct
6 Correct 25 ms 25340 KB Output is correct
7 Correct 36 ms 25340 KB Output is correct
8 Correct 23 ms 25340 KB Output is correct
9 Correct 1486 ms 25600 KB Output is correct
10 Correct 1731 ms 25600 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 46496 KB Output is correct
2 Execution timed out 4045 ms 48556 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23804 KB Output is correct
2 Correct 959 ms 25340 KB Output is correct
3 Correct 669 ms 25340 KB Output is correct
4 Correct 22 ms 25340 KB Output is correct
5 Correct 27 ms 25340 KB Output is correct
6 Correct 25 ms 25340 KB Output is correct
7 Correct 36 ms 25340 KB Output is correct
8 Correct 23 ms 25340 KB Output is correct
9 Correct 1486 ms 25600 KB Output is correct
10 Correct 1731 ms 25600 KB Output is correct
11 Correct 1673 ms 48556 KB Output is correct
12 Correct 458 ms 48556 KB Output is correct
13 Execution timed out 4027 ms 48556 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23804 KB Output is correct
2 Correct 959 ms 25340 KB Output is correct
3 Correct 669 ms 25340 KB Output is correct
4 Correct 22 ms 25340 KB Output is correct
5 Correct 27 ms 25340 KB Output is correct
6 Correct 25 ms 25340 KB Output is correct
7 Correct 36 ms 25340 KB Output is correct
8 Correct 23 ms 25340 KB Output is correct
9 Correct 1486 ms 25600 KB Output is correct
10 Correct 1731 ms 25600 KB Output is correct
11 Correct 1673 ms 48556 KB Output is correct
12 Correct 458 ms 48556 KB Output is correct
13 Execution timed out 4027 ms 48556 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23804 KB Output is correct
2 Correct 959 ms 25340 KB Output is correct
3 Correct 669 ms 25340 KB Output is correct
4 Correct 22 ms 25340 KB Output is correct
5 Correct 27 ms 25340 KB Output is correct
6 Correct 25 ms 25340 KB Output is correct
7 Correct 36 ms 25340 KB Output is correct
8 Correct 23 ms 25340 KB Output is correct
9 Correct 1486 ms 25600 KB Output is correct
10 Correct 1731 ms 25600 KB Output is correct
11 Correct 508 ms 46496 KB Output is correct
12 Execution timed out 4045 ms 48556 KB Time limit exceeded
13 Halted 0 ms 0 KB -