#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int st[N], ed[N], sz[N], timer, n;
bool dd[N];
vector<int> adj[N], arr;
void dfs(int u, int p) {
sz[u] = 1;
arr.push_back(u);
st[u] = ++timer;
for(int &v : adj[u]) if (v != p && !dd[v]) {
dfs(v, u);
sz[v] += sz[u];
}
ed[u] = timer;
}
bool scout (int u, int p, int x, int y) {
if (u == x || u == y) return true;
bool ret = 0;
for(int &v : adj[u]) if (v != p && !dd[v]) ret |= scout(v, u, x, y);
return ret;
}
void calc (int node, int x, bool on) {
// cout << node << " " << x << endl;
arr.clear();
timer = 0;
dfs(node, node);
if (arr.size() == 2 && on) {
int a = arr[0], b = arr[1];
for(int i = 0; i < adj[a].size(); i++) if (adj[a][i] == b) {
adj[a].erase(adj[a].begin() + i);
}
for(int i = 0; i < adj[b].size(); i++) if (adj[b][i] == a) {
adj[b].erase(adj[b].begin() + i);
}
adj[a].push_back(x); adj[x].push_back(a);
adj[b].push_back(x); adj[x].push_back(b);
return;
}
if (arr.size() == 1) {
bool add = 1;
for(int &v : adj[node]) {
assert(x != node && node != v && v != x);
if (Query(x, node, v) != x) continue;
for(int i = 0; i < adj[node].size(); i++) if (adj[node][i] == v) {
adj[node].erase(adj[node].begin() + i);
}
for(int i = 0; i < adj[v].size(); i++) if (adj[v][i] == node) {
adj[v].erase(adj[v].begin() + i);
}
adj[node].push_back(x); adj[x].push_back(node);
adj[v].push_back(x); adj[x].push_back(v);
return;
}
adj[node].push_back(x);
adj[x].push_back(node);
return;
}
int worst = n, a = 0, b = 0;
for(int &j : arr) for(int &k : arr) if (st[j] < st[k]) {
int cost;
if (ed[j] >= st[k]) cost = max({sz[k], sz[j] - sz[k], n - sz[j]});
else cost = max({sz[k], sz[j], n - sz[j] - sz[k]});
if (cost < worst) {
worst = cost;
a = j; b = k;
}
}
// cout << worst << " " << a << " " << b << endl;
// assert(a != b && b != x && x != a);
int c = Query(a, b, x);
if (c == x) {
for(int &v : adj[a]) if (!dd[v]) dd[v] = scout(v, a, a, b) ^ 1;
for(int &v : adj[b]) if (!dd[v]) dd[v] = scout(v, b, a, b) ^ 1;
calc(a, x, 1);
return;
}
for(int &v : adj[c]) if (!dd[v]) dd[v] = scout(v, c, a, b);
calc(c, x, on);
}
void Solve(int N) {
n = N;
for(int i = 0; i < n; i++) adj[i].clear(), dd[i] = 0;
adj[0].push_back(1);
adj[1].push_back(0);
for(int cur = 2; cur < n; cur++) {
calc(0, cur, 0);
for(int i = 0; i < cur; i++) dd[i] = 0;
}
// cout << endl;
//
// for(int i = 0; i < n; i++) for(int &j : adj[i]) if (i < j) {
// cout << i << " " << j << endl;
// }
// return;
for(int i = 0; i < n; i++) for(int &j : adj[i]) if (i < j) Bridge(i, j);
}
Compilation message
meetings.cpp: In function 'void calc(int, int, bool)':
meetings.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i < adj[a].size(); i++) if (adj[a][i] == b) {
| ~~^~~~~~~~~~~~~~~
meetings.cpp:41:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < adj[b].size(); i++) if (adj[b][i] == a) {
| ~~^~~~~~~~~~~~~~~
meetings.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i < adj[node].size(); i++) if (adj[node][i] == v) {
| ~~^~~~~~~~~~~~~~~~~~
meetings.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | for(int i = 0; i < adj[v].size(); i++) if (adj[v][i] == node) {
| ~~^~~~~~~~~~~~~~~
meetings.cpp:49:10: warning: unused variable 'add' [-Wunused-variable]
49 | bool add = 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [4] |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [4] |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
344 KB |
Output is correct |
| 6 |
Correct |
0 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
600 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Incorrect |
0 ms |
344 KB |
Wrong Answer [4] |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
227 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
