#include "meetings.h"
#include<vector>
#include<algorithm>
using namespace std;
int is_in[2121], P[2121], W[2121][2121];
struct xy { int x, y; };
bool sort_y(xy a, xy b) { if (a.y != b.y)return a.y > b.y; return a.x < b.x; }
vector<xy>edge[2121];
int C[2121], nown, mx, cent;
void dfs(int w, int bef) {
C[w] = 1;
int flag = 1;
for (xy E : edge[w]) if (!E.y && E.x != bef) {
dfs(E.x, w);
if (C[E.x] > nown / 2)flag = 0;
C[w] += C[E.x];
}
if (nown - C[w] > nown / 2)flag = 0;
if (flag)cent = w;
}
void connect(int p, int c, int who) {
int x = Query(p, c, who);
if (x == p)P[c] = P[who] = p;
else if (x == c)P[c] = p, P[who] = c;
else if (x == who)P[c] = who, P[who] = p;
else is_in[x] = 1, P[c] = P[who] = x, P[x] = p;
}
void disconnect(int a, int b) { edge[a][W[a][b]].y = edge[b][W[b][a]].y = 1; }
void Solve(int N) {
connect(0, 1, 2);
is_in[0] = is_in[1] = is_in[2] = 1;
for (int now = 3; now < N; now++) {
if (is_in[now])continue;
nown = 1;
for (int i = 1; i < N; i++) {
if (is_in[i]) {
W[P[i]][i] = edge[P[i]].size(); edge[P[i]].push_back({ i,0 });
W[i][P[i]] = edge[i].size(); edge[i].push_back({ P[i],0 });
nown++;
}
}
int root = 0;
while (1) {
mx = cent = 0;
dfs(root, -1);
if (C[root] == 1) {
P[now] = root; break;
}
vector<xy>L; int cnt = 0;
for (xy E : edge[cent]) if (!E.y) {
L.push_back({ E.x,(C[E.x] < C[cent] ? C[E.x] : nown - C[cent]) });
}
sort(L.begin(), L.end(), sort_y);
if (L.size() == 1) {
int who = L[0].x, p, c;
if (P[cent] == who) p = who, c = cent;
else p = cent, c = who;
connect(p, c, now);
break;
}
else {
int ck = 0; root = cent;
for (int i = 1; i < L.size(); i += 2) {
int a = L[i - 1].x, b = L[i].x;
int x = Query(a, b, now);
if (x == cent) disconnect(a, cent), disconnect(b, cent), nown -= L[i - 1].y, nown -= L[i].y;
else {
if (x == a) disconnect(a, cent), root = a, nown = L[i - 1].y;
else if (x == b) disconnect(b, cent), root = b, nown = L[i].y;
else {
int y = Query(a, x, cent); ck = 1;
if (y == x) {
if (P[a] == cent) { P[a] = P[now] = x; P[x] = cent; is_in[x] = 1; }
else { P[cent] = P[now] = x; P[x] = a; is_in[x] = 1; }
}
else {
if (P[b] == cent) { P[b] = P[now] = x; P[x] = cent; is_in[x] = 1; }
else { P[cent] = P[now] = x; P[x] = b; is_in[x] = 1; }
}
}
break;
}
}
if (ck) break;
}
}
is_in[now] = 1;
for (int i = 0; i < N; i++)edge[i].clear();
}
for (int i = 1; i < N; i++) {
if(i<P[i]) Bridge(i, P[i]);
else Bridge(P[i], i);
}
}
Compilation message
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < L.size(); i += 2) {
~~^~~~~~~~~~
meetings.cpp:49:21: warning: unused variable 'cnt' [-Wunused-variable]
vector<xy>L; int cnt = 0;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
380 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
508 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
4 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
4 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
380 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
508 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
4 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
4 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
632 KB |
Output is correct |
17 |
Correct |
5 ms |
504 KB |
Output is correct |
18 |
Correct |
5 ms |
632 KB |
Output is correct |
19 |
Correct |
5 ms |
504 KB |
Output is correct |
20 |
Correct |
5 ms |
636 KB |
Output is correct |
21 |
Correct |
5 ms |
632 KB |
Output is correct |
22 |
Correct |
5 ms |
504 KB |
Output is correct |
23 |
Correct |
5 ms |
632 KB |
Output is correct |
24 |
Correct |
5 ms |
632 KB |
Output is correct |
25 |
Correct |
6 ms |
632 KB |
Output is correct |
26 |
Correct |
5 ms |
504 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
4 ms |
380 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
508 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
376 KB |
Output is correct |
7 |
Correct |
5 ms |
504 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
4 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
504 KB |
Output is correct |
11 |
Correct |
5 ms |
504 KB |
Output is correct |
12 |
Correct |
4 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
632 KB |
Output is correct |
15 |
Correct |
5 ms |
632 KB |
Output is correct |
16 |
Correct |
5 ms |
632 KB |
Output is correct |
17 |
Correct |
5 ms |
504 KB |
Output is correct |
18 |
Correct |
5 ms |
632 KB |
Output is correct |
19 |
Correct |
5 ms |
504 KB |
Output is correct |
20 |
Correct |
5 ms |
636 KB |
Output is correct |
21 |
Correct |
5 ms |
632 KB |
Output is correct |
22 |
Correct |
5 ms |
504 KB |
Output is correct |
23 |
Correct |
5 ms |
632 KB |
Output is correct |
24 |
Correct |
5 ms |
632 KB |
Output is correct |
25 |
Correct |
6 ms |
632 KB |
Output is correct |
26 |
Correct |
5 ms |
504 KB |
Output is correct |
27 |
Correct |
12 ms |
1784 KB |
Output is correct |
28 |
Correct |
12 ms |
1784 KB |
Output is correct |
29 |
Correct |
12 ms |
1784 KB |
Output is correct |
30 |
Correct |
11 ms |
1784 KB |
Output is correct |
31 |
Correct |
11 ms |
1788 KB |
Output is correct |
32 |
Correct |
14 ms |
1656 KB |
Output is correct |
33 |
Correct |
16 ms |
1656 KB |
Output is correct |
34 |
Correct |
16 ms |
1632 KB |
Output is correct |
35 |
Correct |
16 ms |
1656 KB |
Output is correct |
36 |
Correct |
12 ms |
1784 KB |
Output is correct |
37 |
Correct |
14 ms |
1912 KB |
Output is correct |
38 |
Correct |
15 ms |
1792 KB |
Output is correct |
39 |
Correct |
13 ms |
1656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
571 ms |
12544 KB |
Output is correct |
2 |
Correct |
571 ms |
12792 KB |
Output is correct |
3 |
Correct |
580 ms |
12792 KB |
Output is correct |
4 |
Correct |
550 ms |
12792 KB |
Output is correct |
5 |
Correct |
495 ms |
13304 KB |
Output is correct |
6 |
Correct |
420 ms |
12024 KB |
Output is correct |
7 |
Correct |
526 ms |
10360 KB |
Output is correct |
8 |
Correct |
574 ms |
9848 KB |
Output is correct |
9 |
Correct |
526 ms |
9592 KB |
Output is correct |
10 |
Correct |
513 ms |
9464 KB |
Output is correct |
11 |
Correct |
599 ms |
9592 KB |
Output is correct |
12 |
Correct |
582 ms |
12664 KB |
Output is correct |
13 |
Correct |
548 ms |
11000 KB |
Output is correct |
14 |
Correct |
541 ms |
9464 KB |
Output is correct |
15 |
Correct |
508 ms |
9340 KB |
Output is correct |
16 |
Correct |
550 ms |
9484 KB |
Output is correct |
17 |
Correct |
537 ms |
9336 KB |
Output is correct |
18 |
Correct |
536 ms |
8824 KB |
Output is correct |
19 |
Correct |
560 ms |
8764 KB |
Output is correct |
20 |
Correct |
644 ms |
10104 KB |
Output is correct |
21 |
Correct |
649 ms |
9976 KB |
Output is correct |
22 |
Correct |
644 ms |
10104 KB |
Output is correct |
23 |
Correct |
644 ms |
9976 KB |
Output is correct |
24 |
Correct |
624 ms |
10360 KB |
Output is correct |
25 |
Correct |
652 ms |
8952 KB |
Output is correct |
26 |
Correct |
642 ms |
8952 KB |
Output is correct |
27 |
Correct |
664 ms |
8824 KB |
Output is correct |
28 |
Correct |
609 ms |
9464 KB |
Output is correct |
29 |
Correct |
474 ms |
9464 KB |
Output is correct |
30 |
Correct |
535 ms |
9460 KB |
Output is correct |
31 |
Correct |
562 ms |
9464 KB |
Output is correct |
32 |
Correct |
832 ms |
14968 KB |
Output is correct |
33 |
Correct |
630 ms |
8824 KB |
Output is correct |
34 |
Correct |
12 ms |
1784 KB |
Output is correct |
35 |
Correct |
12 ms |
1784 KB |
Output is correct |
36 |
Correct |
12 ms |
1656 KB |
Output is correct |
37 |
Correct |
11 ms |
1784 KB |
Output is correct |
38 |
Correct |
11 ms |
1784 KB |
Output is correct |
39 |
Correct |
13 ms |
1656 KB |
Output is correct |
40 |
Correct |
15 ms |
1660 KB |
Output is correct |
41 |
Correct |
17 ms |
1656 KB |
Output is correct |
42 |
Correct |
17 ms |
1656 KB |
Output is correct |
43 |
Correct |
11 ms |
1784 KB |
Output is correct |
44 |
Correct |
14 ms |
1784 KB |
Output is correct |
45 |
Correct |
14 ms |
1784 KB |
Output is correct |
46 |
Correct |
13 ms |
1656 KB |
Output is correct |
47 |
Correct |
5 ms |
504 KB |
Output is correct |
48 |
Correct |
5 ms |
632 KB |
Output is correct |
49 |
Correct |
5 ms |
504 KB |
Output is correct |
50 |
Correct |
5 ms |
504 KB |
Output is correct |
51 |
Correct |
5 ms |
632 KB |
Output is correct |
52 |
Correct |
5 ms |
504 KB |
Output is correct |
53 |
Correct |
5 ms |
504 KB |
Output is correct |
54 |
Correct |
5 ms |
632 KB |
Output is correct |
55 |
Correct |
5 ms |
504 KB |
Output is correct |
56 |
Correct |
5 ms |
504 KB |
Output is correct |
57 |
Correct |
5 ms |
632 KB |
Output is correct |
58 |
Correct |
5 ms |
632 KB |
Output is correct |
59 |
Correct |
5 ms |
636 KB |
Output is correct |
60 |
Correct |
4 ms |
376 KB |
Output is correct |
61 |
Correct |
5 ms |
376 KB |
Output is correct |
62 |
Correct |
4 ms |
376 KB |
Output is correct |
63 |
Correct |
5 ms |
376 KB |
Output is correct |
64 |
Correct |
5 ms |
376 KB |
Output is correct |
65 |
Correct |
5 ms |
376 KB |
Output is correct |
66 |
Correct |
5 ms |
376 KB |
Output is correct |
67 |
Correct |
4 ms |
504 KB |
Output is correct |
68 |
Correct |
5 ms |
508 KB |
Output is correct |
69 |
Correct |
5 ms |
376 KB |
Output is correct |
70 |
Correct |
5 ms |
504 KB |
Output is correct |
71 |
Correct |
4 ms |
380 KB |
Output is correct |
72 |
Correct |
5 ms |
376 KB |
Output is correct |