답안 #56594 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56594	2018-07-12T01:55:00 Z	kingpig9	낙하산 고리들 (IOI12_rings)	C++11	52 / 100	4000 ms	156556 KB

rings

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #56594

Compilation message

Subtask #1 20.0 / 20.0

Subtask #2 0 / 17.0

Subtask #3 18.0 / 18.0

Subtask #4 14.0 / 14.0

Subtask #5 0 / 31.0

Subtask #1
20.0 / 20.0

Subtask #2
0 / 17.0

Subtask #3
18.0 / 18.0

Subtask #4
14.0 / 14.0

Subtask #5
0 / 31.0