#include "meetings.h"
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
constexpr int dy[4]={ -1,0,1,0 };
constexpr int dx[4]={ 0,-1,0,1 };
namespace{
map<pair<pair<int,int>,int>,int> memo;
int query(int u, int v, int w){
if(u > v) swap(u, v);
if(v > w) swap(v, w);
if(u > v) swap(u, v);
if(u == v) return v;
if(v == w) return v;
if(memo.count({{u,v},w})) return memo[{{u,v},w}];
return memo[{{u,v},w}] = Query(u, v, w);
}
vector<int> e[2000];
bool used[2000];
int sz;
int CentroidDecomposition(int n, int p){ // find one centroid
int ma = 0;
int sum = 1;
rep(i, e[n].size()){
if(e[n][i] == p || used[e[n][i]]) continue;
int ret = CentroidDecomposition(e[n][i], n);
if(ret <= 0) return ret;
chmax(ma, ret);
sum += ret;
}
if(ma <= sz / 2 && sz - sum <= sz / 2) return -n;
return sum;
}
int size(int n, int p){
int sum = 1;
rep(i, e[n].size()){
if(e[n][i] == p || used[e[n][i]]) continue;
sum += size(e[n][i], n);
}
return sum;
}
void fill(int n, int p){
used[n] = true;
sz--;
rep(i, e[n].size()){
if(e[n][i] == p || used[e[n][i]]) continue;
fill(e[n][i], n);
}
}
void erase(vector<int> &v, int x){
rep(i, v.size()){
if(v[i] == x){
v.erase(v.begin()+i);
break;
}
}
}
};
void Solve(int N) {
vector<int> v;
rep(i, N) v.pb(i);
random_device seed_gen;
mt19937 engine(seed_gen());
shuffle(all(v), engine);
e[v[0]].pb(v[1]);
e[v[1]].pb(v[0]);
for(int i=2; i<N; i++){
sz = i;
memset(used, false, sizeof(used));
bool flg = true;
int root = v[0];
while(flg){
int u = -CentroidDecomposition(root, -1); // O(N^2 log N)
assert(u >= 0);
vector<pair<int,int>> tmp;
rep(j, e[u].size()){
if(used[e[u][j]]) continue;
tmp.pb({size(e[u][j], u), e[u][j]});
}
sort(all(tmp));
reverse(all(tmp));
if(tmp.size() == 0){
e[u].pb(v[i]);
e[v[i]].pb(u);
break;
}
bool ok = false;
for(int j=0; j<tmp.size(); j+=2){
if(j+1 == tmp.size()){
if(!ok){
int ret = query(u, tmp[j].second, v[i]);
if(ret == v[i]){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(v[i]);
e[tmp[j].second].pb(v[i]);
e[v[i]].pb(u);
e[v[i]].pb(tmp[j].second);
ok = true;
flg = false;
break;
}
if(ret == tmp[j].second){
ok = true;
root = tmp[j].second;
continue;
}
if(ret != u){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(ret);
e[tmp[j].second].pb(ret);
e[ret].pb(u);
e[ret].pb(tmp[j].second);
ok = true;
flg = false;
for(int k=i+1; k<v.size(); k++){
if(v[k] == ret) swap(v[k], v[i]);
}
break;
}
}
fill(tmp[j].second, u);
}
else{
if(!ok){
int ret = query(tmp[j].second, tmp[j+1].second, v[i]);
if(ret == v[i]){
int ret2 = query(u, tmp[j].second, v[i]);
if(ret2 == v[i]){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(v[i]);
e[tmp[j].second].pb(v[i]);
e[v[i]].pb(u);
e[v[i]].pb(tmp[j].second);
}
else{
erase(e[u], tmp[j+1].second);
erase(e[tmp[j+1].second], u);
e[u].pb(v[i]);
e[tmp[j+1].second].pb(v[i]);
e[v[i]].pb(u);
e[v[i]].pb(tmp[j+1].second);
}
ok = true;
flg = false;
break;
}
if(ret == tmp[j].second){
ok = true;
root = tmp[j].second;
fill(tmp[j+1].second, u);
continue;
}
if(ret == tmp[j+1].second){
ok = true;
root = tmp[j+1].second;
fill(tmp[j].second, u);
continue;
}
if(ret != u){
int ret2 = query(u, tmp[j].second, ret);
if(ret2 == ret){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(ret);
e[tmp[j].second].pb(ret);
e[ret].pb(u);
e[ret].pb(tmp[j].second);
}
else{
erase(e[u], tmp[j+1].second);
erase(e[tmp[j+1].second], u);
e[u].pb(ret);
e[tmp[j+1].second].pb(ret);
e[ret].pb(u);
e[ret].pb(tmp[j+1].second);
}
for(int k=i+1; k<v.size(); k++){
if(v[k] == ret) swap(v[k], v[i]);
}
ok = true;
flg = false;
break;
}
fill(tmp[j].second, u);
fill(tmp[j+1].second, u);
}
else{
fill(tmp[j].second, u);
fill(tmp[j+1].second, u);
}
}
}
if(!ok){
e[u].pb(v[i]);
e[v[i]].pb(u);
break;
}
used[u] = true;
sz--;
}
/*rep(j, N){
cout << j << ":";
rep(k, e[j].size()){
cout << " " << e[j][k];
}
cout << endl;
}*/
}
vector<pair<int,int>> ans;
rep(i, N){
rep(j, e[i].size()){
ans.pb({min(i, e[i][j]), max(i, e[i][j])});
}
}
sort(all(ans));
ans.erase(unique(all(ans)), ans.end());
rep(i, N-1){
Bridge(ans[i].first, ans[i].second);
}
}
Compilation message
meetings.cpp: In function 'int {anonymous}::CentroidDecomposition(int, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:37:9: note: in expansion of macro 'rep'
37 | rep(i, e[n].size()){
| ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
meetings.cpp:37:9: note: in expansion of macro 'rep'
37 | rep(i, e[n].size()){
| ^~~
meetings.cpp: In function 'int {anonymous}::size(int, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:49:9: note: in expansion of macro 'rep'
49 | rep(i, e[n].size()){
| ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
meetings.cpp:49:9: note: in expansion of macro 'rep'
49 | rep(i, e[n].size()){
| ^~~
meetings.cpp: In function 'void {anonymous}::fill(int, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:58:9: note: in expansion of macro 'rep'
58 | rep(i, e[n].size()){
| ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
meetings.cpp:58:9: note: in expansion of macro 'rep'
58 | rep(i, e[n].size()){
| ^~~
meetings.cpp: In function 'void {anonymous}::erase(std::vector<int>&, int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:64:9: note: in expansion of macro 'rep'
64 | rep(i, v.size()){
| ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
meetings.cpp:64:9: note: in expansion of macro 'rep'
64 | rep(i, v.size()){
| ^~~
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:75:5: note: in expansion of macro 'rep'
75 | rep(i, N) v.pb(i);
| ^~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:92:13: note: in expansion of macro 'rep'
92 | rep(j, e[u].size()){
| ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
meetings.cpp:92:13: note: in expansion of macro 'rep'
92 | rep(j, e[u].size()){
| ^~~
meetings.cpp:104:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j=0; j<tmp.size(); j+=2){
| ~^~~~~~~~~~~
meetings.cpp:105:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | if(j+1 == tmp.size()){
| ~~~~^~~~~~~~~~~~~
meetings.cpp:133:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for(int k=i+1; k<v.size(); k++){
| ~^~~~~~~~~
meetings.cpp:196:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | for(int k=i+1; k<v.size(); k++){
| ~^~~~~~~~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:232:5: note: in expansion of macro 'rep'
232 | rep(i, N){
| ^~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:233:9: note: in expansion of macro 'rep'
233 | rep(j, e[i].size()){
| ^~~
meetings.cpp:14:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ~~~^~~~
meetings.cpp:233:9: note: in expansion of macro 'rep'
233 | rep(j, e[i].size()){
| ^~~
meetings.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
| ^
meetings.cpp:239:5: note: in expansion of macro 'rep'
239 | rep(i, N-1){
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
2 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
328 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
328 KB |
Output is correct |
12 |
Correct |
1 ms |
380 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
2 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
328 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
328 KB |
Output is correct |
12 |
Correct |
1 ms |
380 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
328 KB |
Output is correct |
17 |
Correct |
1 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
328 KB |
Output is correct |
19 |
Correct |
1 ms |
328 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
1 ms |
328 KB |
Output is correct |
22 |
Correct |
1 ms |
328 KB |
Output is correct |
23 |
Correct |
1 ms |
328 KB |
Output is correct |
24 |
Correct |
2 ms |
328 KB |
Output is correct |
25 |
Correct |
1 ms |
328 KB |
Output is correct |
26 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
328 KB |
Output is correct |
3 |
Correct |
1 ms |
328 KB |
Output is correct |
4 |
Correct |
2 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
328 KB |
Output is correct |
9 |
Correct |
1 ms |
328 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
328 KB |
Output is correct |
12 |
Correct |
1 ms |
380 KB |
Output is correct |
13 |
Correct |
1 ms |
328 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
328 KB |
Output is correct |
17 |
Correct |
1 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
328 KB |
Output is correct |
19 |
Correct |
1 ms |
328 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
1 ms |
328 KB |
Output is correct |
22 |
Correct |
1 ms |
328 KB |
Output is correct |
23 |
Correct |
1 ms |
328 KB |
Output is correct |
24 |
Correct |
2 ms |
328 KB |
Output is correct |
25 |
Correct |
1 ms |
328 KB |
Output is correct |
26 |
Correct |
1 ms |
328 KB |
Output is correct |
27 |
Correct |
8 ms |
456 KB |
Output is correct |
28 |
Correct |
9 ms |
456 KB |
Output is correct |
29 |
Correct |
11 ms |
448 KB |
Output is correct |
30 |
Correct |
8 ms |
456 KB |
Output is correct |
31 |
Correct |
9 ms |
456 KB |
Output is correct |
32 |
Correct |
12 ms |
516 KB |
Output is correct |
33 |
Correct |
12 ms |
572 KB |
Output is correct |
34 |
Correct |
14 ms |
592 KB |
Output is correct |
35 |
Correct |
13 ms |
584 KB |
Output is correct |
36 |
Correct |
10 ms |
456 KB |
Output is correct |
37 |
Correct |
14 ms |
484 KB |
Output is correct |
38 |
Correct |
13 ms |
536 KB |
Output is correct |
39 |
Correct |
12 ms |
528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
621 ms |
1540 KB |
Output is correct |
2 |
Correct |
583 ms |
1480 KB |
Output is correct |
3 |
Correct |
532 ms |
1528 KB |
Output is correct |
4 |
Correct |
561 ms |
1496 KB |
Output is correct |
5 |
Correct |
573 ms |
1600 KB |
Output is correct |
6 |
Correct |
593 ms |
1544 KB |
Output is correct |
7 |
Correct |
596 ms |
1808 KB |
Output is correct |
8 |
Correct |
695 ms |
1996 KB |
Output is correct |
9 |
Correct |
630 ms |
2032 KB |
Output is correct |
10 |
Correct |
632 ms |
2276 KB |
Output is correct |
11 |
Correct |
674 ms |
2100 KB |
Output is correct |
12 |
Correct |
768 ms |
1772 KB |
Output is correct |
13 |
Correct |
643 ms |
1752 KB |
Output is correct |
14 |
Correct |
642 ms |
1896 KB |
Output is correct |
15 |
Correct |
558 ms |
1792 KB |
Output is correct |
16 |
Correct |
593 ms |
1848 KB |
Output is correct |
17 |
Correct |
609 ms |
2124 KB |
Output is correct |
18 |
Correct |
529 ms |
1984 KB |
Output is correct |
19 |
Correct |
559 ms |
1888 KB |
Output is correct |
20 |
Correct |
659 ms |
1808 KB |
Output is correct |
21 |
Correct |
642 ms |
2040 KB |
Output is correct |
22 |
Correct |
691 ms |
1812 KB |
Output is correct |
23 |
Correct |
596 ms |
1836 KB |
Output is correct |
24 |
Correct |
675 ms |
1940 KB |
Output is correct |
25 |
Correct |
595 ms |
1908 KB |
Output is correct |
26 |
Correct |
593 ms |
1868 KB |
Output is correct |
27 |
Correct |
594 ms |
1936 KB |
Output is correct |
28 |
Correct |
779 ms |
2112 KB |
Output is correct |
29 |
Correct |
565 ms |
2116 KB |
Output is correct |
30 |
Correct |
600 ms |
2164 KB |
Output is correct |
31 |
Correct |
621 ms |
2024 KB |
Output is correct |
32 |
Correct |
895 ms |
1960 KB |
Output is correct |
33 |
Correct |
755 ms |
1928 KB |
Output is correct |
34 |
Correct |
9 ms |
456 KB |
Output is correct |
35 |
Correct |
9 ms |
456 KB |
Output is correct |
36 |
Correct |
9 ms |
456 KB |
Output is correct |
37 |
Correct |
9 ms |
456 KB |
Output is correct |
38 |
Correct |
10 ms |
456 KB |
Output is correct |
39 |
Correct |
9 ms |
512 KB |
Output is correct |
40 |
Correct |
13 ms |
584 KB |
Output is correct |
41 |
Correct |
14 ms |
568 KB |
Output is correct |
42 |
Correct |
13 ms |
584 KB |
Output is correct |
43 |
Correct |
9 ms |
456 KB |
Output is correct |
44 |
Correct |
12 ms |
584 KB |
Output is correct |
45 |
Correct |
13 ms |
456 KB |
Output is correct |
46 |
Correct |
11 ms |
480 KB |
Output is correct |
47 |
Correct |
1 ms |
328 KB |
Output is correct |
48 |
Correct |
1 ms |
328 KB |
Output is correct |
49 |
Correct |
1 ms |
328 KB |
Output is correct |
50 |
Correct |
1 ms |
328 KB |
Output is correct |
51 |
Correct |
1 ms |
328 KB |
Output is correct |
52 |
Correct |
1 ms |
328 KB |
Output is correct |
53 |
Correct |
1 ms |
328 KB |
Output is correct |
54 |
Correct |
2 ms |
328 KB |
Output is correct |
55 |
Correct |
1 ms |
328 KB |
Output is correct |
56 |
Correct |
1 ms |
328 KB |
Output is correct |
57 |
Correct |
2 ms |
328 KB |
Output is correct |
58 |
Correct |
3 ms |
328 KB |
Output is correct |
59 |
Correct |
1 ms |
328 KB |
Output is correct |
60 |
Correct |
1 ms |
328 KB |
Output is correct |
61 |
Correct |
1 ms |
328 KB |
Output is correct |
62 |
Correct |
1 ms |
328 KB |
Output is correct |
63 |
Correct |
1 ms |
328 KB |
Output is correct |
64 |
Correct |
1 ms |
328 KB |
Output is correct |
65 |
Correct |
2 ms |
380 KB |
Output is correct |
66 |
Correct |
1 ms |
328 KB |
Output is correct |
67 |
Correct |
1 ms |
328 KB |
Output is correct |
68 |
Correct |
1 ms |
328 KB |
Output is correct |
69 |
Correct |
1 ms |
328 KB |
Output is correct |
70 |
Correct |
1 ms |
328 KB |
Output is correct |
71 |
Correct |
1 ms |
384 KB |
Output is correct |
72 |
Correct |
1 ms |
328 KB |
Output is correct |