#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;
int total = 0;
int findSubSize(int u, int p, vector<vector<int>> &G, vector<int> &subSize, vector<bool> &dead)
{
subSize[u] = 1;
for (int v : G[u]) {
if (v == p || dead[v]) continue;
subSize[u] += findSubSize(v, u, G, subSize, dead);
}
return subSize[u];
}
int findCentroid(int u, int p, vector<vector<int>> &G, int treeSize, vector<int> &subSize, vector<bool> &dead)
{
// cerr << u << ' ' << p << ' ' << treeSize << endl;
bool isCentroid = 1;
for (int v : G[u]) {
if (v == p || dead[v]) continue;
if (subSize[v] > treeSize / 2) isCentroid = 0;
}
if (treeSize - subSize[u] > treeSize / 2) isCentroid = 0;
if (isCentroid) return u;
for (int v : G[u]) {
if (v == p || dead[v]) continue;
int cand = findCentroid(v, u, G, treeSize, subSize, dead);
if (cand) return cand;
}
return 0;
}
void addBetween(int u, int v, int w, vector<vector<int>> &G)
{
*find(G[u].begin(), G[u].end(), v) = w;
*find(G[v].begin(), G[v].end(), u) = w;
G[w] = {u, v};
}
void addVertex(int nxt, vector<vector<int>> &G, vector<bool> &found, vector<bool> &dead, vector<int> &subSize)
{
int N = (int) G.size();
fill(dead.begin(), dead.end(), 0);
int root = 0;
while (!found[nxt]) {
int curSize = findSubSize(root, -1, G, subSize, dead);
int centroid = findCentroid(root, -1, G, curSize, subSize, dead);
if (curSize == 1) {
G[centroid].push_back(nxt);
G[nxt].push_back(centroid);
found[nxt] = 1;
return;
}
findSubSize(centroid, -1, G, subSize, dead);
vector<int> cands;
for (int v : G[centroid]) {
if (!dead[v]) cands.push_back(v);
}
sort(cands.begin(), cands.end(), [&](int u, int v) { return subSize[u] > subSize[v]; });
for (int candRoot : cands) {
int mid = Query(centroid, candRoot, nxt); // guaranteed all arguments are distinct
if (mid == centroid) {
continue;
} else if (mid == candRoot) {
root = candRoot, dead[centroid] = 1;
break;
} else if (mid == nxt) {
addBetween(centroid, candRoot, nxt, G);
found[nxt] = 1;
return;
} else {
addBetween(centroid, candRoot, mid, G);
G[mid].push_back(nxt);
G[nxt].push_back(mid);
found[mid] = found[nxt] = 1;
return;
}
}
if (!dead[centroid]) {
G[centroid].push_back(nxt);
G[nxt].push_back(centroid);
found[nxt] = 1;
return;
}
}
}
void Solve(int N)
{
vector<vector<int>> G(N);
G[1].push_back(0);
G[0].push_back(1);
vector<bool> found(N, 0);
found[1] = found[0] = 1;
vector<int> subSize(N);
vector<bool> dead(N);
for (int nxt = 2; nxt < N; ++nxt) {
if (!found[nxt]) {
addVertex(nxt, G, found, dead, subSize);
}
}
// std::cerr << "total " << total << std::endl;
for (int u = 0; u < N; ++u) {
for (int v : G[u]) {
if (u < v) {
Bridge(u, v);
}
}
}
}
Compilation message
meetings.cpp: In function 'void addVertex(int, std::vector<std::vector<int> >&, std::vector<bool>&, std::vector<bool>&, std::vector<int>&)':
meetings.cpp:49:6: warning: unused variable 'N' [-Wunused-variable]
int N = (int) G.size();
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
404 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
248 KB |
Output is correct |
9 |
Correct |
2 ms |
248 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
252 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
404 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
248 KB |
Output is correct |
9 |
Correct |
2 ms |
248 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
252 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
14 |
Correct |
2 ms |
248 KB |
Output is correct |
15 |
Correct |
2 ms |
248 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
248 KB |
Output is correct |
18 |
Correct |
2 ms |
244 KB |
Output is correct |
19 |
Correct |
2 ms |
380 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
380 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
248 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
404 KB |
Output is correct |
4 |
Correct |
2 ms |
248 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
248 KB |
Output is correct |
9 |
Correct |
2 ms |
248 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
252 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
14 |
Correct |
2 ms |
248 KB |
Output is correct |
15 |
Correct |
2 ms |
248 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
248 KB |
Output is correct |
18 |
Correct |
2 ms |
244 KB |
Output is correct |
19 |
Correct |
2 ms |
380 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
380 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
248 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
9 ms |
376 KB |
Output is correct |
28 |
Correct |
10 ms |
376 KB |
Output is correct |
29 |
Correct |
10 ms |
376 KB |
Output is correct |
30 |
Correct |
10 ms |
376 KB |
Output is correct |
31 |
Correct |
9 ms |
376 KB |
Output is correct |
32 |
Correct |
12 ms |
504 KB |
Output is correct |
33 |
Correct |
16 ms |
376 KB |
Output is correct |
34 |
Correct |
22 ms |
376 KB |
Output is correct |
35 |
Correct |
20 ms |
376 KB |
Output is correct |
36 |
Correct |
10 ms |
376 KB |
Output is correct |
37 |
Correct |
14 ms |
504 KB |
Output is correct |
38 |
Correct |
14 ms |
376 KB |
Output is correct |
39 |
Correct |
14 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1030 ms |
852 KB |
Output is correct |
2 |
Correct |
1071 ms |
744 KB |
Output is correct |
3 |
Correct |
1107 ms |
852 KB |
Output is correct |
4 |
Correct |
1039 ms |
840 KB |
Output is correct |
5 |
Correct |
732 ms |
844 KB |
Output is correct |
6 |
Correct |
646 ms |
908 KB |
Output is correct |
7 |
Correct |
894 ms |
860 KB |
Output is correct |
8 |
Correct |
992 ms |
748 KB |
Output is correct |
9 |
Correct |
1076 ms |
776 KB |
Output is correct |
10 |
Correct |
1022 ms |
856 KB |
Output is correct |
11 |
Correct |
1204 ms |
860 KB |
Output is correct |
12 |
Correct |
992 ms |
820 KB |
Output is correct |
13 |
Correct |
805 ms |
812 KB |
Output is correct |
14 |
Correct |
950 ms |
760 KB |
Output is correct |
15 |
Correct |
867 ms |
860 KB |
Output is correct |
16 |
Correct |
907 ms |
984 KB |
Output is correct |
17 |
Correct |
1082 ms |
888 KB |
Output is correct |
18 |
Correct |
831 ms |
856 KB |
Output is correct |
19 |
Correct |
913 ms |
720 KB |
Output is correct |
20 |
Correct |
946 ms |
768 KB |
Output is correct |
21 |
Correct |
1074 ms |
980 KB |
Output is correct |
22 |
Correct |
1036 ms |
760 KB |
Output is correct |
23 |
Correct |
992 ms |
804 KB |
Output is correct |
24 |
Correct |
982 ms |
760 KB |
Output is correct |
25 |
Correct |
1006 ms |
900 KB |
Output is correct |
26 |
Correct |
977 ms |
940 KB |
Output is correct |
27 |
Correct |
1020 ms |
952 KB |
Output is correct |
28 |
Correct |
1163 ms |
908 KB |
Output is correct |
29 |
Correct |
875 ms |
984 KB |
Output is correct |
30 |
Correct |
969 ms |
868 KB |
Output is correct |
31 |
Correct |
1077 ms |
868 KB |
Output is correct |
32 |
Correct |
1387 ms |
968 KB |
Output is correct |
33 |
Correct |
1102 ms |
960 KB |
Output is correct |
34 |
Correct |
10 ms |
376 KB |
Output is correct |
35 |
Correct |
9 ms |
376 KB |
Output is correct |
36 |
Correct |
11 ms |
376 KB |
Output is correct |
37 |
Correct |
9 ms |
504 KB |
Output is correct |
38 |
Correct |
9 ms |
376 KB |
Output is correct |
39 |
Correct |
12 ms |
376 KB |
Output is correct |
40 |
Correct |
19 ms |
376 KB |
Output is correct |
41 |
Correct |
22 ms |
504 KB |
Output is correct |
42 |
Correct |
20 ms |
376 KB |
Output is correct |
43 |
Correct |
10 ms |
376 KB |
Output is correct |
44 |
Correct |
14 ms |
504 KB |
Output is correct |
45 |
Correct |
14 ms |
504 KB |
Output is correct |
46 |
Correct |
14 ms |
504 KB |
Output is correct |
47 |
Correct |
2 ms |
376 KB |
Output is correct |
48 |
Correct |
15 ms |
252 KB |
Output is correct |
49 |
Correct |
2 ms |
248 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
2 ms |
376 KB |
Output is correct |
52 |
Correct |
2 ms |
248 KB |
Output is correct |
53 |
Correct |
2 ms |
376 KB |
Output is correct |
54 |
Correct |
2 ms |
376 KB |
Output is correct |
55 |
Correct |
2 ms |
376 KB |
Output is correct |
56 |
Correct |
2 ms |
376 KB |
Output is correct |
57 |
Correct |
2 ms |
376 KB |
Output is correct |
58 |
Correct |
2 ms |
252 KB |
Output is correct |
59 |
Correct |
2 ms |
376 KB |
Output is correct |
60 |
Correct |
2 ms |
248 KB |
Output is correct |
61 |
Correct |
2 ms |
248 KB |
Output is correct |
62 |
Correct |
2 ms |
248 KB |
Output is correct |
63 |
Correct |
2 ms |
376 KB |
Output is correct |
64 |
Correct |
2 ms |
248 KB |
Output is correct |
65 |
Correct |
2 ms |
376 KB |
Output is correct |
66 |
Correct |
2 ms |
248 KB |
Output is correct |
67 |
Correct |
2 ms |
248 KB |
Output is correct |
68 |
Correct |
2 ms |
376 KB |
Output is correct |
69 |
Correct |
2 ms |
248 KB |
Output is correct |
70 |
Correct |
2 ms |
248 KB |
Output is correct |
71 |
Correct |
2 ms |
376 KB |
Output is correct |
72 |
Correct |
2 ms |
248 KB |
Output is correct |