#include <bits/stdc++.h>
#ifndef skeletaZaPrezident
#include "meetings.h"
#endif
#define query Query
#define bridge Bridge
#define solve Solve
#define int32_t int
#define int64_t long long
const int32_t MAX_N = 2000;
#ifdef skeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w) {
std::cout << u << " " << v << " " << w << '\n' << std::flush;
int32_t res;
std::cin >> res;
return res;
}
void bridge(int32_t u, int32_t v) {
std::cout << "edge: " << u << " " << v << '\n' << std::flush;
}
#endif
#ifndef sekeletaZaPrezident
int32_t query(int32_t u, int32_t v, int32_t w);
void bridge(int32_t u, int32_t v);
#endif
std::map< int32_t, int32_t > asked[MAX_N + 5][MAX_N + 5];
int32_t ask_query(int32_t x, int32_t y, int32_t z) {
int32_t a[] = { x, y, z };
std::sort(a, a + 3);
if(asked[a[0]][a[1]].count(a[2]) == 0) {
asked[a[0]][a[1]][a[2]] = query(a[0], a[1], a[2]);
}
return asked[a[0]][a[1]][a[2]];
}
struct Vertex {
bool vis;
int32_t subtreeSize;
std::vector< int32_t > adjList;
Vertex() : vis(false), subtreeSize(1) {}
};
bool isInserted[MAX_N + 5];
Vertex t[MAX_N + 5];
bool sort_by_subtree_size(int32_t u, int32_t v) {
return t[u].subtreeSize > t[v].subtreeSize;
}
void init(int32_t n) {
for(int32_t i = 0; i < n; i++) {
t[i].vis = false;
}
}
void compute_subtree_sizes(int32_t v, int32_t par) {
t[v].subtreeSize = 1;
for(auto &x : t[v].adjList) {
if(x == par || t[x].vis) {
continue;
}
compute_subtree_sizes(x, v);
t[v].subtreeSize += t[x].subtreeSize;
}
}
int32_t find_centroid(int32_t v, int32_t par, int32_t target) {
int32_t maxSubtree = -1, ind = -1;
for(auto &x : t[v].adjList) {
if(x == par || t[x].vis) {
if(t[x].vis) {
t[x].subtreeSize = 0;
}
continue;
}
if(t[x].subtreeSize > maxSubtree) {
maxSubtree = t[x].subtreeSize;
ind = x;
}
}
if(ind != -1 && maxSubtree > target / 2) {
return find_centroid(ind, v, target);
}
return v;
}
void solve_vertex(int32_t root, int32_t v) {
compute_subtree_sizes(root, -1);
int32_t centroid = find_centroid(root, -1, t[root].subtreeSize);
compute_subtree_sizes(centroid, -1);
int32_t aux;
std::sort(t[centroid].adjList.begin(), t[centroid].adjList.end(), sort_by_subtree_size);
for(int32_t i = 0; i < (int32_t) t[centroid].adjList.size(); i++) {
if(i == (int32_t) t[centroid].adjList.size() - 1) {
aux = ask_query(centroid, t[centroid].adjList[i], v);
if(aux == v) {
t[t[centroid].adjList[i]].adjList.push_back(v);
t[v].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
return;
}
if(aux == t[centroid].adjList[i]) {
t[centroid].vis = true;
solve_vertex(t[centroid].adjList[i], v);
return;
}
if(aux != centroid) {
solve_vertex(aux, v);
t[t[centroid].adjList[i]].adjList.push_back(aux);
t[aux].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(aux);
t[aux].adjList.push_back(centroid);
isInserted[aux] = true;
return;
}
break;
}
aux = ask_query(t[centroid].adjList[i], t[centroid].adjList[i + 1], v);
// v is on the path from t[centroid].adjList[i] to t[centroid].adjList[i + 1]
if(aux == v) {
aux = ask_query(t[centroid].adjList[i], centroid, v);
if(aux == centroid) {
t[t[centroid].adjList[i + 1]].adjList.push_back(v);
t[v].adjList.push_back(t[centroid].adjList[i + 1]);
t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
return;
}
t[t[centroid].adjList[i]].adjList.push_back(v);
t[v].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
return;
}
if(aux == t[centroid].adjList[i]) {
t[centroid].vis = true;
solve_vertex(t[centroid].adjList[i], v);
return;
}
if(aux == t[centroid].adjList[i + 1]) {
t[centroid].vis = true;
solve_vertex(t[centroid].adjList[i + 1], v);
return;
}
if(aux != centroid) {
solve_vertex(aux, v);
int32_t aux2 = ask_query(t[centroid].adjList[i], aux, centroid);
if(aux2 == centroid) {
t[t[centroid].adjList[i + 1]].adjList.push_back(aux);
t[aux].adjList.push_back(t[centroid].adjList[i + 1]);
t[t[centroid].adjList[i + 1]].adjList.erase(std::find(t[t[centroid].adjList[i + 1]].adjList.begin(), t[t[centroid].adjList[i + 1]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i + 1);
t[centroid].adjList.push_back(aux);
t[aux].adjList.push_back(centroid);
}
else {
t[t[centroid].adjList[i]].adjList.push_back(aux);
t[aux].adjList.push_back(t[centroid].adjList[i]);
t[t[centroid].adjList[i]].adjList.erase(std::find(t[t[centroid].adjList[i]].adjList.begin(), t[t[centroid].adjList[i]].adjList.end(), centroid));
t[centroid].adjList.erase(t[centroid].adjList.begin() + i);
t[centroid].adjList.push_back(aux);
t[aux].adjList.push_back(centroid);
}
isInserted[aux] = true;
return;
}
}
t[centroid].adjList.push_back(v);
t[v].adjList.push_back(centroid);
}
void solve(int32_t n) {
t[0].adjList.push_back(1);
t[1].adjList.push_back(0);
// solve for each node
for(int32_t i = 2; i < n; i++) {
if(isInserted[i]) {
continue;
}
init(n);
solve_vertex(0, i);
}
for(int32_t i = 0; i < n; i++) {
for(auto &x : t[i].adjList) {
if(x > i) {
bridge(i, x);
}
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
189224 KB |
Output is correct |
2 |
Correct |
155 ms |
189224 KB |
Output is correct |
3 |
Correct |
153 ms |
189304 KB |
Output is correct |
4 |
Correct |
157 ms |
189236 KB |
Output is correct |
5 |
Correct |
158 ms |
189324 KB |
Output is correct |
6 |
Correct |
156 ms |
189176 KB |
Output is correct |
7 |
Correct |
162 ms |
189224 KB |
Output is correct |
8 |
Correct |
156 ms |
189176 KB |
Output is correct |
9 |
Correct |
152 ms |
189248 KB |
Output is correct |
10 |
Correct |
152 ms |
189204 KB |
Output is correct |
11 |
Correct |
154 ms |
189140 KB |
Output is correct |
12 |
Correct |
153 ms |
189228 KB |
Output is correct |
13 |
Correct |
154 ms |
189260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
189224 KB |
Output is correct |
2 |
Correct |
155 ms |
189224 KB |
Output is correct |
3 |
Correct |
153 ms |
189304 KB |
Output is correct |
4 |
Correct |
157 ms |
189236 KB |
Output is correct |
5 |
Correct |
158 ms |
189324 KB |
Output is correct |
6 |
Correct |
156 ms |
189176 KB |
Output is correct |
7 |
Correct |
162 ms |
189224 KB |
Output is correct |
8 |
Correct |
156 ms |
189176 KB |
Output is correct |
9 |
Correct |
152 ms |
189248 KB |
Output is correct |
10 |
Correct |
152 ms |
189204 KB |
Output is correct |
11 |
Correct |
154 ms |
189140 KB |
Output is correct |
12 |
Correct |
153 ms |
189228 KB |
Output is correct |
13 |
Correct |
154 ms |
189260 KB |
Output is correct |
14 |
Correct |
155 ms |
189372 KB |
Output is correct |
15 |
Correct |
157 ms |
189176 KB |
Output is correct |
16 |
Correct |
153 ms |
189176 KB |
Output is correct |
17 |
Correct |
156 ms |
189176 KB |
Output is correct |
18 |
Correct |
159 ms |
189352 KB |
Output is correct |
19 |
Correct |
153 ms |
189252 KB |
Output is correct |
20 |
Correct |
160 ms |
189224 KB |
Output is correct |
21 |
Correct |
154 ms |
189160 KB |
Output is correct |
22 |
Correct |
153 ms |
189296 KB |
Output is correct |
23 |
Correct |
153 ms |
189224 KB |
Output is correct |
24 |
Correct |
162 ms |
189276 KB |
Output is correct |
25 |
Correct |
154 ms |
189176 KB |
Output is correct |
26 |
Correct |
154 ms |
189180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
189224 KB |
Output is correct |
2 |
Correct |
155 ms |
189224 KB |
Output is correct |
3 |
Correct |
153 ms |
189304 KB |
Output is correct |
4 |
Correct |
157 ms |
189236 KB |
Output is correct |
5 |
Correct |
158 ms |
189324 KB |
Output is correct |
6 |
Correct |
156 ms |
189176 KB |
Output is correct |
7 |
Correct |
162 ms |
189224 KB |
Output is correct |
8 |
Correct |
156 ms |
189176 KB |
Output is correct |
9 |
Correct |
152 ms |
189248 KB |
Output is correct |
10 |
Correct |
152 ms |
189204 KB |
Output is correct |
11 |
Correct |
154 ms |
189140 KB |
Output is correct |
12 |
Correct |
153 ms |
189228 KB |
Output is correct |
13 |
Correct |
154 ms |
189260 KB |
Output is correct |
14 |
Correct |
155 ms |
189372 KB |
Output is correct |
15 |
Correct |
157 ms |
189176 KB |
Output is correct |
16 |
Correct |
153 ms |
189176 KB |
Output is correct |
17 |
Correct |
156 ms |
189176 KB |
Output is correct |
18 |
Correct |
159 ms |
189352 KB |
Output is correct |
19 |
Correct |
153 ms |
189252 KB |
Output is correct |
20 |
Correct |
160 ms |
189224 KB |
Output is correct |
21 |
Correct |
154 ms |
189160 KB |
Output is correct |
22 |
Correct |
153 ms |
189296 KB |
Output is correct |
23 |
Correct |
153 ms |
189224 KB |
Output is correct |
24 |
Correct |
162 ms |
189276 KB |
Output is correct |
25 |
Correct |
154 ms |
189176 KB |
Output is correct |
26 |
Correct |
154 ms |
189180 KB |
Output is correct |
27 |
Correct |
162 ms |
189408 KB |
Output is correct |
28 |
Correct |
161 ms |
189304 KB |
Output is correct |
29 |
Correct |
164 ms |
189304 KB |
Output is correct |
30 |
Correct |
159 ms |
189468 KB |
Output is correct |
31 |
Correct |
158 ms |
189404 KB |
Output is correct |
32 |
Correct |
193 ms |
189432 KB |
Output is correct |
33 |
Correct |
168 ms |
189476 KB |
Output is correct |
34 |
Correct |
170 ms |
189464 KB |
Output is correct |
35 |
Correct |
167 ms |
189432 KB |
Output is correct |
36 |
Correct |
168 ms |
189432 KB |
Output is correct |
37 |
Correct |
164 ms |
189400 KB |
Output is correct |
38 |
Correct |
163 ms |
189304 KB |
Output is correct |
39 |
Correct |
163 ms |
189372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
848 ms |
190288 KB |
Output is correct |
2 |
Correct |
830 ms |
190328 KB |
Output is correct |
3 |
Correct |
817 ms |
190392 KB |
Output is correct |
4 |
Correct |
815 ms |
190372 KB |
Output is correct |
5 |
Correct |
593 ms |
190288 KB |
Output is correct |
6 |
Correct |
544 ms |
190368 KB |
Output is correct |
7 |
Correct |
755 ms |
191124 KB |
Output is correct |
8 |
Correct |
877 ms |
191352 KB |
Output is correct |
9 |
Correct |
871 ms |
191392 KB |
Output is correct |
10 |
Correct |
860 ms |
191480 KB |
Output is correct |
11 |
Correct |
947 ms |
191500 KB |
Output is correct |
12 |
Correct |
781 ms |
190340 KB |
Output is correct |
13 |
Correct |
648 ms |
190456 KB |
Output is correct |
14 |
Correct |
822 ms |
190820 KB |
Output is correct |
15 |
Correct |
744 ms |
191032 KB |
Output is correct |
16 |
Correct |
813 ms |
190972 KB |
Output is correct |
17 |
Correct |
898 ms |
191600 KB |
Output is correct |
18 |
Correct |
721 ms |
190968 KB |
Output is correct |
19 |
Correct |
764 ms |
191008 KB |
Output is correct |
20 |
Correct |
810 ms |
190932 KB |
Output is correct |
21 |
Correct |
824 ms |
190968 KB |
Output is correct |
22 |
Correct |
818 ms |
190836 KB |
Output is correct |
23 |
Correct |
830 ms |
190952 KB |
Output is correct |
24 |
Correct |
813 ms |
190996 KB |
Output is correct |
25 |
Correct |
864 ms |
190908 KB |
Output is correct |
26 |
Correct |
830 ms |
190968 KB |
Output is correct |
27 |
Correct |
895 ms |
190840 KB |
Output is correct |
28 |
Correct |
1065 ms |
191480 KB |
Output is correct |
29 |
Correct |
801 ms |
191608 KB |
Output is correct |
30 |
Correct |
856 ms |
191444 KB |
Output is correct |
31 |
Correct |
895 ms |
191372 KB |
Output is correct |
32 |
Correct |
1121 ms |
190584 KB |
Output is correct |
33 |
Correct |
874 ms |
190780 KB |
Output is correct |
34 |
Correct |
161 ms |
189440 KB |
Output is correct |
35 |
Correct |
162 ms |
189360 KB |
Output is correct |
36 |
Correct |
160 ms |
189388 KB |
Output is correct |
37 |
Correct |
161 ms |
189356 KB |
Output is correct |
38 |
Correct |
160 ms |
189428 KB |
Output is correct |
39 |
Correct |
159 ms |
189352 KB |
Output is correct |
40 |
Correct |
167 ms |
189476 KB |
Output is correct |
41 |
Correct |
171 ms |
189560 KB |
Output is correct |
42 |
Correct |
171 ms |
189500 KB |
Output is correct |
43 |
Correct |
161 ms |
189304 KB |
Output is correct |
44 |
Correct |
164 ms |
189268 KB |
Output is correct |
45 |
Correct |
165 ms |
189408 KB |
Output is correct |
46 |
Correct |
163 ms |
189432 KB |
Output is correct |
47 |
Correct |
152 ms |
189136 KB |
Output is correct |
48 |
Correct |
153 ms |
189304 KB |
Output is correct |
49 |
Correct |
154 ms |
189156 KB |
Output is correct |
50 |
Correct |
154 ms |
189204 KB |
Output is correct |
51 |
Correct |
153 ms |
189176 KB |
Output is correct |
52 |
Correct |
153 ms |
189176 KB |
Output is correct |
53 |
Correct |
155 ms |
189416 KB |
Output is correct |
54 |
Correct |
152 ms |
189304 KB |
Output is correct |
55 |
Correct |
153 ms |
189304 KB |
Output is correct |
56 |
Correct |
152 ms |
189176 KB |
Output is correct |
57 |
Correct |
153 ms |
189348 KB |
Output is correct |
58 |
Correct |
152 ms |
189224 KB |
Output is correct |
59 |
Correct |
152 ms |
189176 KB |
Output is correct |
60 |
Correct |
152 ms |
189112 KB |
Output is correct |
61 |
Correct |
152 ms |
189412 KB |
Output is correct |
62 |
Correct |
151 ms |
189224 KB |
Output is correct |
63 |
Correct |
153 ms |
189176 KB |
Output is correct |
64 |
Correct |
154 ms |
189176 KB |
Output is correct |
65 |
Correct |
151 ms |
189176 KB |
Output is correct |
66 |
Correct |
151 ms |
189296 KB |
Output is correct |
67 |
Correct |
150 ms |
189224 KB |
Output is correct |
68 |
Correct |
155 ms |
189352 KB |
Output is correct |
69 |
Correct |
154 ms |
189304 KB |
Output is correct |
70 |
Correct |
156 ms |
189176 KB |
Output is correct |
71 |
Correct |
153 ms |
189284 KB |
Output is correct |
72 |
Correct |
154 ms |
189320 KB |
Output is correct |