oj.uz

Submission #56594

# Submission time Handle Problem Language Result Execution time Memory
56594 2018-07-12T01:55:00 Z kingpig9 Parachute rings (IOI12_rings) C++11
52 / 100
 4000 ms 156556 KB 
#include <bits/stdc++.h>
//#include "rings.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e6 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int N;
int status;
vector<int> adj[MAXN];
unordered_set<int> verts[5];	//verts[min(degree, 4)]

#define end enddd
int ntest;

struct union_find {
	int exc;	//vertex to be exluced
	bool ok;	//is this answer good?
	int ncyc, szcyc;	//# of cycles, size of one of the cycles if there is any.
	int par[MAXN];
	int start[MAXN], end[MAXN];
	int nedge[MAXN];	//lol I forgot the case of CYCLES!! :(
	int sz[MAXN];

	void reset (int e) {
		exc = e;
		ok = true;
		ncyc = 0;
		for (int i = 0; i < N; i++) {
			par[i] = i;
			start[i] = i;
			end[i] = i;
			nedge[i] = 0;
			sz[i] = 1;
		}
	}

	int find (int x) {
		return x == par[x] ? x : par[x] = find(par[x]);
	}

	void merge (int a, int b) {
		if ((!ok && status > 2) || a == exc || b == exc) {
			return;
		}

		int fa = find(a), fb = find(b);
		if (fa == fb) {
			ncyc -= (sz[fa] == nedge[fa]);
			nedge[fa]++;
			ncyc += (sz[fa] == nedge[fa]);
			if (sz[fa] == nedge[fa]) {
				szcyc = sz[fa];
			}
			ok = false;
			return;
		}

		if (a != end[fa]) {
			swap(start[fa], end[fa]);
		}
		if (b != start[fb]) {
			swap(start[fb], end[fb]);
		}

		if (a != end[fa] || b != start[fb]) {
			ok = false;
			return;
		}

		par[fb] = fa;
		end[fa] = end[fb];

		ncyc -= (sz[fa] == nedge[fa]);
		ncyc -= (sz[fb] == nedge[fb]);
		nedge[fa] = nedge[fa] + nedge[fb] + 1;
		sz[fa] += sz[fb];
		ncyc += (sz[fa] == nedge[fa]);
		if (sz[fa] == nedge[fa]) {
			assert(status >= 3);
			szcyc = sz[fa];
		}
	}
} uf[4];

void Init (int nnnn) {
	N = nnnn;

	//ok now do something else
	for (int i = 0; i < N; i++) {
		verts[0].insert(i);
	}

	ntest = 1;
	uf[0].reset(-1);
	status = 0;
}

void settest (vector<int> v) {
	ntest = v.size();

	for (int i = 0; i < ntest; i++) {
		uf[i].reset(v[i]);
		for (int x = 0; x < N; x++) {
			for (int y : adj[x]) {
				if (x < y) {
					uf[i].merge(x, y);
				}
			}
		}
	}
}

void Link (int a, int b) {
	if (status == -1) {
		return;
	}

	for (int v : {a, b}) {
		assert(verts[min(4, (int) adj[v].size())].erase(v));
	}
	adj[a].push_back(b);
	adj[b].push_back(a);
	for (int v : {a, b}) {
		verts[min(4, (int) adj[v].size())].insert(v);
	}

	//recalc status
	status = 4;
	while (verts[status].empty()) {
		status--;
	}

	for (int i = 0; i < ntest; i++) {
		uf[i].merge(a, b);	//hmm "merge" is pretty bad for this case...
	}

	if (status == 3) {
		if (ntest == 1) {
			int v = *verts[3].begin();
			settest(vector<int> {v, adj[v][0], adj[v][1], adj[v][2]});
		}
	} else if (status == 4) {
		if (verts[4].size() > 1) {
			status = -1;
			return;
		}
		//otherwise, leave it to this one
		if (ntest == 4) {
			settest(vector<int> {*verts[4].begin()});
		}
	}
}

int CountCritical() {
	if (status == -1) {
		return 0;
	}

	int ans = 0;
	if (status <= 2) {
		if (uf[0].ncyc == 0) {
			ans = N;
		} else if (uf[0].ncyc == 1) {
			ans = uf[0].szcyc;
		} else {
			ans = 0;
		}
	} else {
		for (int i = 0; i < ntest; i++) {
			ans += uf[i].ok;
		}
	}

	if (ans == 0) {
		status = -1;
	}
	return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 32 ms 24820 KB Output is correct
3 Correct 29 ms 24920 KB Output is correct
4 Correct 22 ms 24920 KB Output is correct
5 Correct 25 ms 24920 KB Output is correct
6 Correct 36 ms 24920 KB Output is correct
7 Correct 24 ms 24924 KB Output is correct
8 Correct 26 ms 24924 KB Output is correct
9 Correct 28 ms 25056 KB Output is correct
10 Correct 27 ms 25056 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 82384 KB Output is correct
2 Correct 3503 ms 156556 KB Output is correct
3 Correct 605 ms 156556 KB Output is correct
4 Correct 3878 ms 156556 KB Output is correct
5 Correct 3956 ms 156556 KB Output is correct
6 Execution timed out 4024 ms 156556 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 32 ms 24820 KB Output is correct
3 Correct 29 ms 24920 KB Output is correct
4 Correct 22 ms 24920 KB Output is correct
5 Correct 25 ms 24920 KB Output is correct
6 Correct 36 ms 24920 KB Output is correct
7 Correct 24 ms 24924 KB Output is correct
8 Correct 26 ms 24924 KB Output is correct
9 Correct 28 ms 25056 KB Output is correct
10 Correct 27 ms 25056 KB Output is correct
11 Correct 29 ms 156556 KB Output is correct
12 Correct 35 ms 156556 KB Output is correct
13 Correct 36 ms 156556 KB Output is correct
14 Correct 31 ms 156556 KB Output is correct
15 Correct 34 ms 156556 KB Output is correct
16 Correct 32 ms 156556 KB Output is correct
17 Correct 27 ms 156556 KB Output is correct
18 Correct 29 ms 156556 KB Output is correct
19 Correct 34 ms 156556 KB Output is correct
20 Correct 38 ms 156556 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 32 ms 24820 KB Output is correct
3 Correct 29 ms 24920 KB Output is correct
4 Correct 22 ms 24920 KB Output is correct
5 Correct 25 ms 24920 KB Output is correct
6 Correct 36 ms 24920 KB Output is correct
7 Correct 24 ms 24924 KB Output is correct
8 Correct 26 ms 24924 KB Output is correct
9 Correct 28 ms 25056 KB Output is correct
10 Correct 27 ms 25056 KB Output is correct
11 Correct 29 ms 156556 KB Output is correct
12 Correct 35 ms 156556 KB Output is correct
13 Correct 36 ms 156556 KB Output is correct
14 Correct 31 ms 156556 KB Output is correct
15 Correct 34 ms 156556 KB Output is correct
16 Correct 32 ms 156556 KB Output is correct
17 Correct 27 ms 156556 KB Output is correct
18 Correct 29 ms 156556 KB Output is correct
19 Correct 34 ms 156556 KB Output is correct
20 Correct 38 ms 156556 KB Output is correct
21 Correct 67 ms 156556 KB Output is correct
22 Correct 92 ms 156556 KB Output is correct
23 Correct 143 ms 156556 KB Output is correct
24 Correct 157 ms 156556 KB Output is correct
25 Correct 62 ms 156556 KB Output is correct
26 Correct 152 ms 156556 KB Output is correct
27 Correct 134 ms 156556 KB Output is correct
28 Correct 72 ms 156556 KB Output is correct
29 Correct 70 ms 156556 KB Output is correct
30 Correct 304 ms 156556 KB Output is correct

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 23800 KB Output is correct
2 Correct 32 ms 24820 KB Output is correct
3 Correct 29 ms 24920 KB Output is correct
4 Correct 22 ms 24920 KB Output is correct
5 Correct 25 ms 24920 KB Output is correct
6 Correct 36 ms 24920 KB Output is correct
7 Correct 24 ms 24924 KB Output is correct
8 Correct 26 ms 24924 KB Output is correct
9 Correct 28 ms 25056 KB Output is correct
10 Correct 27 ms 25056 KB Output is correct
11 Correct 1259 ms 82384 KB Output is correct
12 Correct 3503 ms 156556 KB Output is correct
13 Correct 605 ms 156556 KB Output is correct
14 Correct 3878 ms 156556 KB Output is correct
15 Correct 3956 ms 156556 KB Output is correct
16 Execution timed out 4024 ms 156556 KB Time limit exceeded
17 Halted 0 ms 0 KB -