답안 #33904 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33904	2017-11-05T00:10:10 Z	imeimi2000	Simurgh (IOI17_simurgh)	C++14	100 / 100	166 ms	7864 KB

simurgh

#include "simurgh.h"
#include <algorithm>

using namespace std;
typedef pair<int, int> pi;

struct road {
	int i, x;
};

int n, m;
const int MAXM = 500 * 499 / 2;
vector<road> edge[500];
pi es[MAXM];

bool dfsTree[MAXM];
bool backGraph[MAXM];
vector<int> dfsQ;
int par[500];
int parEdge[500];
int dep[500];
int back[500];
int backEdge[500];
int ord = 0, base;

int royal[MAXM];
int sub[500];
int uf[500];

void dfs(int x, int p) {
	dep[x] = ++ord;
	back[x] = dep[x];
	backEdge[x] = -1;
	for (road i : edge[x]) {
		if (dep[i.x] != 0) {
			if (i.x != p && dep[i.x] < back[x]) {
				back[x] = dep[i.x];
				backEdge[x] = i.i;
			}
			continue;
		}
		dfsTree[i.i] = true;
		dfsQ.push_back(i.i);
		par[i.x] = x;
		parEdge[i.x] = i.i;
		dfs(i.x, x);
		if (back[i.x] == dep[i.x]) royal[i.i] = 1;
		else if (back[i.x] < back[x]) {
			back[x] = back[i.x];
			backEdge[x] = backEdge[i.x];
		}
	}
	if (back[x] < dep[x]) backGraph[backEdge[x]] = true;
}

int find(int x) {
	if (uf[x] != x) return uf[x] = find(uf[x]);
	return x;
}

bool merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return false;
	uf[x] = y;
	return true;
}

int question(const vector<int> &vt) {
	vector<int> qs;
	int other = 0;
	for (int i = 0; i < n; ++i) uf[i] = i;
	for (int i : vt) {
		qs.push_back(i);
		merge(es[i].first, es[i].second);
	}
	for (int i : dfsQ) {
		if (merge(es[i].first, es[i].second)) {
			qs.push_back(i);
			if (royal[i] == 1) ++other;
		}
	}
	return count_common_roads(qs) - other;
}

void bsearch(const vector<int> &vt, int s, int e, int c) {
	if (c == 0) {
		for (int i = s; i <= e; ++i) royal[vt[i]] = -1;
		return;
	}
	if (c == e - s + 1) {
		for (int i = s; i <= e; ++i) royal[vt[i]] = 1;
		return;
	}
	vector<int> qs;
	int m = (s + e) / 2;
	for (int i = s; i <= m; ++i) qs.push_back(vt[i]);
	int d = question(qs);
	bsearch(vt, s, m, d);
	bsearch(vt, m + 1, e, c - d);
}

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
	n = N;
	m = u.size();
	for (int i = 0; i < m; ++i) {
		es[i] = pi(u[i], v[i]);
		edge[u[i]].push_back({ i, v[i] });
		edge[v[i]].push_back({ i, u[i] });
	}
	dfs(0, -1);
	base = count_common_roads(dfsQ);
	vector<pi> es;
	for (int i = 0; i < m; ++i) {
		if (backGraph[i]) es.push_back(pi(min(dep[u[i]], dep[v[i]]), i));
	}
	sort(es.begin(), es.end());
	for (pi i : es) {
		int s = u[i.second], e = v[i.second];
		if (dep[s] < dep[e]) swap(s, e);
		int j = s;
		bool allZero = true;
		while (par[j] != e) {
			if (royal[parEdge[j]] == 0) {
				vector<int> qs;
				for (int k : dfsQ) {
					if (k != parEdge[j]) qs.push_back(k);
				}
				qs.push_back(i.second);
				sub[j] = count_common_roads(qs) - base;
				if (sub[j] != 0) {
					allZero = false;
					royal[parEdge[j]] = -sub[j];
					royal[i.second] = sub[j];
				}
			}
			else allZero = false;
			j = par[j];
		}

		vector<int> qs;
		for (int k : dfsQ) {
			if (k != parEdge[j]) qs.push_back(k);
		}
		qs.push_back(i.second);
		sub[j] = count_common_roads(qs) - base;
		if (royal[parEdge[j]] != 0) {
			allZero = false;
			royal[i.second] = royal[parEdge[j]] + 2 * sub[j];
		}
		else if (sub[j] != 0) {
			allZero = false;
			royal[parEdge[j]] = -sub[j];
			royal[i.second] = sub[j];
		}
		if (allZero) {
			j = s;
			while (j != e) {
				royal[parEdge[j]] = -1;
				j = par[j];
			}
			royal[i.second] = -1;
			continue;
		}
		j = s;
		while (j != e) {
			if (royal[parEdge[j]] == 0) royal[parEdge[j]] = royal[i.second] - 2 * sub[j];
			j = par[j];
		}
	}

	for (int i = 0; i < n; ++i) {
		vector<int> es;
		for (road j : edge[i]) {
			if (royal[j.i] == 0) es.push_back(j.i);
		}
		bsearch(es, 0, es.size() - 1, question(es));
	}
	vector<int> ret;
	for (int i = 0; i < m; ++i) {
		if (royal[i] == 1) ret.push_back(i);
	}
	return ret;
}

Subtask #1
13.0 / 13.0

#	결과	메모리	Grader output
1	Correct	3668 KB	correct
2	Correct	3668 KB	correct
3	Correct	3668 KB	correct
4	Correct	3668 KB	correct
5	Correct	3668 KB	correct
6	Correct	3668 KB	correct
7	Correct	3668 KB	correct
8	Correct	3668 KB	correct
9	Correct	3668 KB	correct
10	Correct	3668 KB	correct
11	Correct	3668 KB	correct
12	Correct	3668 KB	correct
13	Correct	3668 KB	correct

Subtask #2
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	3668 KB	correct
2	Correct	3668 KB	correct
3	Correct	3668 KB	correct
4	Correct	3668 KB	correct
5	Correct	3668 KB	correct
6	Correct	3668 KB	correct
7	Correct	3668 KB	correct
8	Correct	3668 KB	correct
9	Correct	3668 KB	correct
10	Correct	3668 KB	correct
11	Correct	3668 KB	correct
12	Correct	3668 KB	correct
13	Correct	3668 KB	correct
14	Correct	3668 KB	correct
15	Correct	3668 KB	correct
16	Correct	3668 KB	correct
17	Correct	3668 KB	correct
18	Correct	3668 KB	correct
19	Correct	3668 KB	correct
20	Correct	3668 KB	correct
21	Correct	3668 KB	correct
22	Correct	3668 KB	correct
23	Correct	3668 KB	correct
24	Correct	3668 KB	correct
25	Correct	3668 KB	correct
26	Correct	3668 KB	correct
27	Correct	3668 KB	correct
28	Correct	3668 KB	correct
29	Correct	3668 KB	correct
30	Correct	3668 KB	correct
31	Correct	3668 KB	correct
32	Correct	3668 KB	correct
33	Correct	3668 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3668 KB	correct
2	Correct	0 ms	3668 KB	correct
3	Correct	0 ms	3668 KB	correct
4	Correct	0 ms	3668 KB	correct
5	Correct	0 ms	3668 KB	correct
6	Correct	0 ms	3668 KB	correct
7	Correct	0 ms	3668 KB	correct
8	Correct	0 ms	3668 KB	correct
9	Correct	0 ms	3668 KB	correct
10	Correct	0 ms	3668 KB	correct
11	Correct	0 ms	3668 KB	correct
12	Correct	0 ms	3668 KB	correct
13	Correct	0 ms	3668 KB	correct
14	Correct	0 ms	3668 KB	correct
15	Correct	0 ms	3668 KB	correct
16	Correct	0 ms	3668 KB	correct
17	Correct	0 ms	3668 KB	correct
18	Correct	0 ms	3668 KB	correct
19	Correct	0 ms	3668 KB	correct
20	Correct	0 ms	3668 KB	correct
21	Correct	0 ms	3668 KB	correct
22	Correct	0 ms	3668 KB	correct
23	Correct	0 ms	3668 KB	correct
24	Correct	0 ms	3668 KB	correct
25	Correct	0 ms	3668 KB	correct
26	Correct	0 ms	3668 KB	correct
27	Correct	0 ms	3668 KB	correct
28	Correct	0 ms	3668 KB	correct
29	Correct	0 ms	3668 KB	correct
30	Correct	0 ms	3668 KB	correct
31	Correct	0 ms	3668 KB	correct
32	Correct	0 ms	3668 KB	correct
33	Correct	0 ms	3668 KB	correct
34	Correct	33 ms	4612 KB	correct
35	Correct	33 ms	4600 KB	correct
36	Correct	29 ms	4496 KB	correct
37	Correct	6 ms	3800 KB	correct
38	Correct	33 ms	4608 KB	correct
39	Correct	26 ms	4560 KB	correct
40	Correct	23 ms	4496 KB	correct
41	Correct	29 ms	4612 KB	correct
42	Correct	29 ms	4612 KB	correct
43	Correct	13 ms	4380 KB	correct
44	Correct	6 ms	4104 KB	correct
45	Correct	13 ms	4232 KB	correct
46	Correct	13 ms	4092 KB	correct
47	Correct	6 ms	3932 KB	correct
48	Correct	3 ms	3668 KB	correct
49	Correct	3 ms	3800 KB	correct
50	Correct	6 ms	3932 KB	correct
51	Correct	13 ms	4232 KB	correct
52	Correct	13 ms	4104 KB	correct
53	Correct	9 ms	4092 KB	correct
54	Correct	13 ms	4380 KB	correct
55	Correct	13 ms	4236 KB	correct
56	Correct	13 ms	4236 KB	correct
57	Correct	13 ms	4236 KB	correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3668 KB	correct
2	Correct	0 ms	3668 KB	correct
3	Correct	96 ms	6632 KB	correct
4	Correct	153 ms	7864 KB	correct
5	Correct	159 ms	7864 KB	correct
6	Correct	149 ms	7864 KB	correct
7	Correct	113 ms	7864 KB	correct
8	Correct	113 ms	7864 KB	correct
9	Correct	153 ms	7864 KB	correct
10	Correct	156 ms	7864 KB	correct
11	Correct	153 ms	7864 KB	correct
12	Correct	166 ms	7864 KB	correct
13	Correct	0 ms	3668 KB	correct
14	Correct	119 ms	7864 KB	correct
15	Correct	166 ms	7864 KB	correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3668 KB	correct
2	Correct	0 ms	3668 KB	correct
3	Correct	0 ms	3668 KB	correct
4	Correct	0 ms	3668 KB	correct
5	Correct	0 ms	3668 KB	correct
6	Correct	0 ms	3668 KB	correct
7	Correct	0 ms	3668 KB	correct
8	Correct	0 ms	3668 KB	correct
9	Correct	0 ms	3668 KB	correct
10	Correct	0 ms	3668 KB	correct
11	Correct	0 ms	3668 KB	correct
12	Correct	0 ms	3668 KB	correct
13	Correct	0 ms	3668 KB	correct
14	Correct	0 ms	3668 KB	correct
15	Correct	0 ms	3668 KB	correct
16	Correct	0 ms	3668 KB	correct
17	Correct	0 ms	3668 KB	correct
18	Correct	0 ms	3668 KB	correct
19	Correct	0 ms	3668 KB	correct
20	Correct	0 ms	3668 KB	correct
21	Correct	0 ms	3668 KB	correct
22	Correct	0 ms	3668 KB	correct
23	Correct	0 ms	3668 KB	correct
24	Correct	0 ms	3668 KB	correct
25	Correct	0 ms	3668 KB	correct
26	Correct	0 ms	3668 KB	correct
27	Correct	0 ms	3668 KB	correct
28	Correct	0 ms	3668 KB	correct
29	Correct	0 ms	3668 KB	correct
30	Correct	0 ms	3668 KB	correct
31	Correct	0 ms	3668 KB	correct
32	Correct	0 ms	3668 KB	correct
33	Correct	0 ms	3668 KB	correct
34	Correct	33 ms	4612 KB	correct
35	Correct	33 ms	4600 KB	correct
36	Correct	29 ms	4496 KB	correct
37	Correct	6 ms	3800 KB	correct
38	Correct	33 ms	4608 KB	correct
39	Correct	26 ms	4560 KB	correct
40	Correct	23 ms	4496 KB	correct
41	Correct	29 ms	4612 KB	correct
42	Correct	29 ms	4612 KB	correct
43	Correct	13 ms	4380 KB	correct
44	Correct	6 ms	4104 KB	correct
45	Correct	13 ms	4232 KB	correct
46	Correct	13 ms	4092 KB	correct
47	Correct	6 ms	3932 KB	correct
48	Correct	3 ms	3668 KB	correct
49	Correct	3 ms	3800 KB	correct
50	Correct	6 ms	3932 KB	correct
51	Correct	13 ms	4232 KB	correct
52	Correct	13 ms	4104 KB	correct
53	Correct	9 ms	4092 KB	correct
54	Correct	13 ms	4380 KB	correct
55	Correct	13 ms	4236 KB	correct
56	Correct	13 ms	4236 KB	correct
57	Correct	13 ms	4236 KB	correct
58	Correct	0 ms	3668 KB	correct
59	Correct	0 ms	3668 KB	correct
60	Correct	96 ms	6632 KB	correct
61	Correct	153 ms	7864 KB	correct
62	Correct	159 ms	7864 KB	correct
63	Correct	149 ms	7864 KB	correct
64	Correct	113 ms	7864 KB	correct
65	Correct	113 ms	7864 KB	correct
66	Correct	153 ms	7864 KB	correct
67	Correct	156 ms	7864 KB	correct
68	Correct	153 ms	7864 KB	correct
69	Correct	166 ms	7864 KB	correct
70	Correct	0 ms	3668 KB	correct
71	Correct	119 ms	7864 KB	correct
72	Correct	166 ms	7864 KB	correct
73	Correct	0 ms	3668 KB	correct
74	Correct	136 ms	7864 KB	correct
75	Correct	159 ms	7800 KB	correct
76	Correct	63 ms	5280 KB	correct
77	Correct	136 ms	7864 KB	correct
78	Correct	146 ms	7864 KB	correct
79	Correct	136 ms	7864 KB	correct
80	Correct	159 ms	7800 KB	correct
81	Correct	106 ms	7512 KB	correct
82	Correct	156 ms	7800 KB	correct
83	Correct	106 ms	6096 KB	correct
84	Correct	69 ms	6652 KB	correct
85	Correct	69 ms	6540 KB	correct
86	Correct	56 ms	5428 KB	correct
87	Correct	39 ms	5168 KB	correct
88	Correct	39 ms	4696 KB	correct
89	Correct	39 ms	4548 KB	correct
90	Correct	39 ms	4500 KB	correct
91	Correct	16 ms	3800 KB	correct
92	Correct	9 ms	3668 KB	correct
93	Correct	69 ms	6540 KB	correct
94	Correct	46 ms	5428 KB	correct
95	Correct	49 ms	5380 KB	correct
96	Correct	29 ms	4516 KB	correct
97	Correct	36 ms	4696 KB	correct
98	Correct	39 ms	5168 KB	correct
99	Correct	36 ms	4580 KB	correct
100	Correct	23 ms	3948 KB	correct
101	Correct	9 ms	3668 KB	correct
102	Correct	56 ms	5848 KB	correct
103	Correct	56 ms	5848 KB	correct
104	Correct	49 ms	5700 KB	correct
105	Correct	49 ms	5700 KB	correct

답안 #33904

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 17.0 / 17.0

Subtask #3 21.0 / 21.0

Subtask #4 19.0 / 19.0

Subtask #5 30.0 / 30.0

Subtask #1
13.0 / 13.0

Subtask #2
17.0 / 17.0

Subtask #3
21.0 / 21.0

Subtask #4
19.0 / 19.0

Subtask #5
30.0 / 30.0