#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;
for (xy E : edge[w]) if (!E.y && E.x != bef) {
dfs(E.x, w);
C[w] += C[E.x];
}
if (C[w] <= nown / 2 && mx < C[w]) mx = C[w], 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[E.x] < C[cent] ? 0 : C[cent]) });
sort(L.begin(), L.end(), sort_y);
if (L.size() == 1) {
int who = L[0].x, p, c;
if (C[who] > C[cent]) p = who, c = cent;
else p = cent, c = who;
connect(p, c, now);
break;
}
else {
int ck = 0; root = cent;
for (int i = 0; i < L.size(); i += 2) {
int a = L[i].x, b = L[i + 1].x;
int x = Query(a, b, now);
if (x == cent) disconnect(a, cent), disconnect(b, cent);
else {
if (x == a) disconnect(a, cent), root = a;
else if (x == b) disconnect(b, cent), root = b;
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:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < L.size(); i += 2) {
~~^~~~~~~~~~
meetings.cpp:43:21: warning: unused variable 'cnt' [-Wunused-variable]
vector<xy>L; int cnt = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [4] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
760 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
