답안 #51940 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51940	2018-06-22T17:14:08 Z	aome	Simurgh (IOI17_simurgh)	C++17	100 / 100	407 ms	20632 KB

simurgh

#include <bits/stdc++.h>
#include "simurgh.h"

using namespace std;

const int N = 510;
const int M = 510 * 510 / 2;

int n, m;
int pset[N];
int deg[N];
int label[N][N];
int par[N], h[N];
int visit_edge[M];
bool visit[N];
vector<int> G[N];
vector<int> vtree;

int find(int u) { 
	return u == pset[u] ? u : pset[u] = find(pset[u]); 
}

bool join(int u, int v) {
	u = find(u), v = find(v), pset[u] = v; return u != v;
}

void dfs(int u) {
	visit[u] = 1;
	for (auto v : G[u]) {
		if (visit[v]) continue;
		vtree.push_back(label[u][v]);
		par[v] = u, h[v] = h[u] + 1, dfs(v);
	}
}


vector<int> find_roads(int _n, vector<int> u, vector<int> v) {
	n = _n, m = u.size();
	for (int i = 0; i < m; ++i) {
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
		label[u[i]][v[i]] = label[v[i]][u[i]] = i;
	}
	dfs(0);
	int val = count_common_roads(vtree);
	for (int i = 0; i < m; ++i) {
		if (h[u[i]] > h[v[i]]) swap(u[i], v[i]);
		int cur = v[i];
		vector<int> vec;
		while (cur != u[i]) {
			int tmp = cur; cur = par[cur];
			vec.push_back(label[cur][tmp]);
		}
		bool flag = 0;
		for (auto j : vec) flag |= !visit_edge[j];
		if (!flag || vec.size() == 1) continue;
		int id = -1;
		for (auto j : vec) if (visit_edge[j]) id = j;
		if (id == -1) {
			for (auto j : vec) {
				vector<int> ask = vtree;
				for (auto &k : ask) if (k == j) k = i;
				int tmp = count_common_roads(ask);
				if (tmp != val) {
					visit_edge[i] = (tmp > val) + 1;
					visit_edge[j] = 3 ^ visit_edge[i];
					// 1 : not loyal, 2 : loyal
				}
			}
			if (!visit_edge[i]) visit_edge[i] = 1;
			for (auto j : vec) {
				if (!visit_edge[j]) visit_edge[j] = visit_edge[i];
			}
		}
		else {
			vector<int> ask = vtree;
			for (auto &j : ask) if (j == id) j = i;
			int tmp = count_common_roads(ask);
			if (tmp == val) visit_edge[i] = visit_edge[id];
			else visit_edge[i] = 3 ^ visit_edge[id];
			for (auto j : vec) {
				if (!visit_edge[j]) {
					vector<int> ask = vtree;
					for (auto &k : ask) if (k == j) k = i;
					int tmp = count_common_roads(ask);
					if (tmp == val) visit_edge[j] = visit_edge[i];
					else visit_edge[j] = 3 ^ visit_edge[i];
				}
			} 
		}
	}
	for (auto i : vtree) {
		if (!visit_edge[i]) visit_edge[i] = 2;
	}
	// for (auto i : vtree) cout << i << ' '; cout << '\n';
	// for (auto i : vtree) cout << visit_edge[i] << ' '; cout << '\n';
	queue<int> qu;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) pset[j] = j;
		vector<int> ask;
		int cnt = 0;
		for (auto j : G[i]) {
			int tmp = label[i][j];
			join(i, j), ask.push_back(tmp), cnt += visit_edge[tmp] == 2;
		}
		for (auto j : vtree) {
			if (join(u[j], v[j])) {
				cnt += visit_edge[j] == 2, ask.push_back(j);
			}
		}
		deg[i] = count_common_roads(ask) - cnt;
		if (deg[i] == 1) qu.push(i);
	}
	// for (int i = 0; i < m; ++i) cout << visit_edge[i] << ' '; cout << '\n'; 
	// for (int i = 0; i < n; ++i) cout << deg[i] << ' '; cout << '\n';
	while (qu.size()) {
		int x = qu.front(); qu.pop();
		if (deg[x] != 1) continue;
		vector<int> vec;
		for (auto i : G[x]) {
			if (!visit_edge[label[x][i]]) {
				vec.push_back(label[x][i]);
			}
		}
		int l = 0, r = vec.size();
		while (l < r) {
			int mid = (l + r) >> 1;
			for (int i = 0; i < n; ++i) pset[i] = i;
			vector<int> ask;
			int cnt = 0;
			for (int i = l; i <= mid; ++i) {
				int tmp = vec[i];
				join(u[tmp], v[tmp]);
				ask.push_back(tmp);
				cnt += visit_edge[tmp] == 2;
			}
			for (auto i : vtree) {
				if (join(u[i], v[i])) {
					ask.push_back(i);
					cnt += visit_edge[i] == 2;
				}
			}
			int tmp = count_common_roads(ask);
			if (tmp == cnt + 1) r = mid;
			else l = mid + 1;
		}
		visit_edge[vec[l]] = 2;
		int y = u[vec[l]];
		if (x == y) y = v[vec[l]];
		deg[y]--;
		if (deg[y] == 1) qu.push(y);
	}
	vector<int> res;
	for (int i = 0; i < m; ++i) {
		if (visit_edge[i] == 2) res.push_back(i);
	}
	return res;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	412 KB	correct
4	Correct	3 ms	416 KB	correct
5	Correct	2 ms	420 KB	correct
6	Correct	2 ms	480 KB	correct
7	Correct	2 ms	560 KB	correct
8	Correct	2 ms	640 KB	correct
9	Correct	2 ms	644 KB	correct
10	Correct	2 ms	652 KB	correct
11	Correct	2 ms	656 KB	correct
12	Correct	2 ms	660 KB	correct
13	Correct	2 ms	660 KB	correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	412 KB	correct
4	Correct	3 ms	416 KB	correct
5	Correct	2 ms	420 KB	correct
6	Correct	2 ms	480 KB	correct
7	Correct	2 ms	560 KB	correct
8	Correct	2 ms	640 KB	correct
9	Correct	2 ms	644 KB	correct
10	Correct	2 ms	652 KB	correct
11	Correct	2 ms	656 KB	correct
12	Correct	2 ms	660 KB	correct
13	Correct	2 ms	660 KB	correct
14	Correct	4 ms	788 KB	correct
15	Correct	3 ms	796 KB	correct
16	Correct	5 ms	836 KB	correct
17	Correct	4 ms	988 KB	correct
18	Correct	4 ms	988 KB	correct
19	Correct	4 ms	988 KB	correct
20	Correct	3 ms	988 KB	correct
21	Correct	4 ms	988 KB	correct
22	Correct	4 ms	988 KB	correct
23	Correct	5 ms	988 KB	correct
24	Correct	4 ms	1060 KB	correct
25	Correct	3 ms	1088 KB	correct
26	Correct	4 ms	1088 KB	correct
27	Correct	3 ms	1088 KB	correct
28	Correct	3 ms	1088 KB	correct
29	Correct	3 ms	1136 KB	correct
30	Correct	3 ms	1136 KB	correct
31	Correct	4 ms	1136 KB	correct
32	Correct	4 ms	1136 KB	correct
33	Correct	4 ms	1136 KB	correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	412 KB	correct
4	Correct	3 ms	416 KB	correct
5	Correct	2 ms	420 KB	correct
6	Correct	2 ms	480 KB	correct
7	Correct	2 ms	560 KB	correct
8	Correct	2 ms	640 KB	correct
9	Correct	2 ms	644 KB	correct
10	Correct	2 ms	652 KB	correct
11	Correct	2 ms	656 KB	correct
12	Correct	2 ms	660 KB	correct
13	Correct	2 ms	660 KB	correct
14	Correct	4 ms	788 KB	correct
15	Correct	3 ms	796 KB	correct
16	Correct	5 ms	836 KB	correct
17	Correct	4 ms	988 KB	correct
18	Correct	4 ms	988 KB	correct
19	Correct	4 ms	988 KB	correct
20	Correct	3 ms	988 KB	correct
21	Correct	4 ms	988 KB	correct
22	Correct	4 ms	988 KB	correct
23	Correct	5 ms	988 KB	correct
24	Correct	4 ms	1060 KB	correct
25	Correct	3 ms	1088 KB	correct
26	Correct	4 ms	1088 KB	correct
27	Correct	3 ms	1088 KB	correct
28	Correct	3 ms	1088 KB	correct
29	Correct	3 ms	1136 KB	correct
30	Correct	3 ms	1136 KB	correct
31	Correct	4 ms	1136 KB	correct
32	Correct	4 ms	1136 KB	correct
33	Correct	4 ms	1136 KB	correct
34	Correct	60 ms	2380 KB	correct
35	Correct	56 ms	2560 KB	correct
36	Correct	44 ms	2592 KB	correct
37	Correct	11 ms	2592 KB	correct
38	Correct	66 ms	3012 KB	correct
39	Correct	72 ms	3100 KB	correct
40	Correct	43 ms	3144 KB	correct
41	Correct	55 ms	3520 KB	correct
42	Correct	65 ms	3736 KB	correct
43	Correct	30 ms	3736 KB	correct
44	Correct	25 ms	3736 KB	correct
45	Correct	27 ms	3736 KB	correct
46	Correct	21 ms	3736 KB	correct
47	Correct	12 ms	3736 KB	correct
48	Correct	5 ms	3736 KB	correct
49	Correct	8 ms	3736 KB	correct
50	Correct	13 ms	3736 KB	correct
51	Correct	22 ms	3760 KB	correct
52	Correct	19 ms	3876 KB	correct
53	Correct	19 ms	3948 KB	correct
54	Correct	24 ms	4264 KB	correct
55	Correct	28 ms	4264 KB	correct
56	Correct	36 ms	4264 KB	correct
57	Correct	26 ms	4348 KB	correct

Subtask #4
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4348 KB	correct
2	Correct	2 ms	4348 KB	correct
3	Correct	185 ms	7644 KB	correct
4	Correct	310 ms	8708 KB	correct
5	Correct	331 ms	8868 KB	correct
6	Correct	323 ms	8868 KB	correct
7	Correct	319 ms	8868 KB	correct
8	Correct	335 ms	8868 KB	correct
9	Correct	353 ms	8868 KB	correct
10	Correct	338 ms	8868 KB	correct
11	Correct	376 ms	8868 KB	correct
12	Correct	368 ms	8868 KB	correct
13	Correct	2 ms	8868 KB	correct
14	Correct	325 ms	8868 KB	correct
15	Correct	327 ms	8868 KB	correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	correct
2	Correct	2 ms	376 KB	correct
3	Correct	2 ms	412 KB	correct
4	Correct	3 ms	416 KB	correct
5	Correct	2 ms	420 KB	correct
6	Correct	2 ms	480 KB	correct
7	Correct	2 ms	560 KB	correct
8	Correct	2 ms	640 KB	correct
9	Correct	2 ms	644 KB	correct
10	Correct	2 ms	652 KB	correct
11	Correct	2 ms	656 KB	correct
12	Correct	2 ms	660 KB	correct
13	Correct	2 ms	660 KB	correct
14	Correct	4 ms	788 KB	correct
15	Correct	3 ms	796 KB	correct
16	Correct	5 ms	836 KB	correct
17	Correct	4 ms	988 KB	correct
18	Correct	4 ms	988 KB	correct
19	Correct	4 ms	988 KB	correct
20	Correct	3 ms	988 KB	correct
21	Correct	4 ms	988 KB	correct
22	Correct	4 ms	988 KB	correct
23	Correct	5 ms	988 KB	correct
24	Correct	4 ms	1060 KB	correct
25	Correct	3 ms	1088 KB	correct
26	Correct	4 ms	1088 KB	correct
27	Correct	3 ms	1088 KB	correct
28	Correct	3 ms	1088 KB	correct
29	Correct	3 ms	1136 KB	correct
30	Correct	3 ms	1136 KB	correct
31	Correct	4 ms	1136 KB	correct
32	Correct	4 ms	1136 KB	correct
33	Correct	4 ms	1136 KB	correct
34	Correct	60 ms	2380 KB	correct
35	Correct	56 ms	2560 KB	correct
36	Correct	44 ms	2592 KB	correct
37	Correct	11 ms	2592 KB	correct
38	Correct	66 ms	3012 KB	correct
39	Correct	72 ms	3100 KB	correct
40	Correct	43 ms	3144 KB	correct
41	Correct	55 ms	3520 KB	correct
42	Correct	65 ms	3736 KB	correct
43	Correct	30 ms	3736 KB	correct
44	Correct	25 ms	3736 KB	correct
45	Correct	27 ms	3736 KB	correct
46	Correct	21 ms	3736 KB	correct
47	Correct	12 ms	3736 KB	correct
48	Correct	5 ms	3736 KB	correct
49	Correct	8 ms	3736 KB	correct
50	Correct	13 ms	3736 KB	correct
51	Correct	22 ms	3760 KB	correct
52	Correct	19 ms	3876 KB	correct
53	Correct	19 ms	3948 KB	correct
54	Correct	24 ms	4264 KB	correct
55	Correct	28 ms	4264 KB	correct
56	Correct	36 ms	4264 KB	correct
57	Correct	26 ms	4348 KB	correct
58	Correct	2 ms	4348 KB	correct
59	Correct	2 ms	4348 KB	correct
60	Correct	185 ms	7644 KB	correct
61	Correct	310 ms	8708 KB	correct
62	Correct	331 ms	8868 KB	correct
63	Correct	323 ms	8868 KB	correct
64	Correct	319 ms	8868 KB	correct
65	Correct	335 ms	8868 KB	correct
66	Correct	353 ms	8868 KB	correct
67	Correct	338 ms	8868 KB	correct
68	Correct	376 ms	8868 KB	correct
69	Correct	368 ms	8868 KB	correct
70	Correct	2 ms	8868 KB	correct
71	Correct	325 ms	8868 KB	correct
72	Correct	327 ms	8868 KB	correct
73	Correct	2 ms	8868 KB	correct
74	Correct	326 ms	9640 KB	correct
75	Correct	340 ms	10696 KB	correct
76	Correct	151 ms	10696 KB	correct
77	Correct	376 ms	11908 KB	correct
78	Correct	407 ms	12832 KB	correct
79	Correct	403 ms	13756 KB	correct
80	Correct	343 ms	14560 KB	correct
81	Correct	284 ms	15064 KB	correct
82	Correct	300 ms	16080 KB	correct
83	Correct	199 ms	16080 KB	correct
84	Correct	181 ms	16080 KB	correct
85	Correct	124 ms	16080 KB	correct
86	Correct	88 ms	16080 KB	correct
87	Correct	62 ms	16080 KB	correct
88	Correct	59 ms	16080 KB	correct
89	Correct	51 ms	16080 KB	correct
90	Correct	51 ms	16080 KB	correct
91	Correct	18 ms	16080 KB	correct
92	Correct	15 ms	16080 KB	correct
93	Correct	116 ms	17752 KB	correct
94	Correct	81 ms	17752 KB	correct
95	Correct	80 ms	17752 KB	correct
96	Correct	47 ms	17752 KB	correct
97	Correct	55 ms	17752 KB	correct
98	Correct	81 ms	18004 KB	correct
99	Correct	62 ms	18004 KB	correct
100	Correct	40 ms	18004 KB	correct
101	Correct	16 ms	18004 KB	correct
102	Correct	151 ms	19244 KB	correct
103	Correct	154 ms	19836 KB	correct
104	Correct	144 ms	20324 KB	correct
105	Correct	147 ms	20632 KB	correct

답안 #51940

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