#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=2005;
set<pair<int,int>> edges;
bool used[MX], vis[MX];
int sz[MX];
int N;
vector<int> adj[MX];
int getSize(int v, int p) {
sz[v]=1;
for(auto u:adj[v]) {
if(u!=p && !used[u]) {
sz[v]+=getSize(u,v);
}
}
return sz[v];
}
int getCen(int v, int p, int s) {
for(auto u:adj[v]) {
if(u!=p && 2*sz[u]>s && !used[u]) {
return getCen(u,v,s);
}
}
return v;
}
map<array<int,3>,int> memo;
int que(int u, int v, int w) {
// cout<<"ask "<<u<<" "<<v<<" "<<w<<endl;
array<int,3> arr={u,v,w};
sort(arr.begin(),arr.end());
if(memo.count(arr)) return memo[arr];
// we can memo here
return memo[arr]=Query(u,v,w);
}
void cdc(int v, int x) {
// cout<<"at node : "<<v<<endl;
int s=getSize(v,v);
// cout<<"size : "<<s<<endl;
int cen=getCen(v,v,s);
getSize(cen,cen);
used[cen]=true;
// cout<<"at cen : "<<cen<<endl;
bool fnd=0;
vector<int> conds;
for(auto u:adj[cen]) {
if(used[u]) continue;
conds.push_back(u);
}
if(conds.size()&1) conds.push_back(cen);
assert(conds.size()<=20);
for(int i=0;i<conds.size();i+=2) {
int u=conds[i],v=conds[i+1];
if(que(u,v,x)!=cen) {
if(que(u,v,x)==u) {
int k=u;
if(sz[u]>1) cdc(u,x);
else {
vis[x]=true;
edges.insert({min(u,x),max(u,x)});
}
} else if(que(u,v,x)==v) {
int k=v;
if(sz[v]>1) cdc(v,x);
else {
vis[x]=true;
edges.insert({min(v,x),max(v,x)});
}
} else {
if(que(u,cen,x)!=cen) {
int k=que(u,cen,x);
if(k==cen) {
assert(false);
} else if(k==u) {
if(sz[u]>1) cdc(u,x);
else {
vis[x]=true;
edges.insert({min(u,x),max(u,x)});
}
} else if(k==x) {
vis[x]=true;
edges.erase({min(u,cen),max(u,cen)});
edges.insert({min(cen,x),max(cen,x)});
edges.insert({min(u,x),max(u,x)});
} else {
vis[x]=true;
vis[k]=true;
edges.erase({min(u,cen),max(u,cen)});
edges.insert({min(cen,k),max(cen,k)});
edges.insert({min(u,k),max(u,k)});
edges.insert({min(x,k),max(x,k)});
}
} else {
int k=que(v,cen,x);
if(k==cen) {
assert(false);
} else if(k==v) {
if(sz[v]>1) cdc(v,x);
else {
vis[x]=true;
edges.insert({min(v,x),max(v,x)});
}
} else if(k==x) {
vis[x]=true;
edges.erase({min(v,cen),max(v,cen)});
edges.insert({min(cen,x),max(cen,x)});
edges.insert({min(v,x),max(v,x)});
} else {
vis[x]=true;
vis[k]=true;
edges.erase({min(v,cen),max(v,cen)});
edges.insert({min(cen,k),max(cen,k)});
edges.insert({min(v,k),max(v,k)});
edges.insert({min(x,k),max(x,k)});
}
}
}
fnd=1;
break;
}
}
if(!fnd) {
vis[x]=true;
edges.insert({min(cen,x),max(cen,x)});
}
}
void prep() {
for(int i=0;i<N;i++) {
used[i]=false;
adj[i].clear();
}
for(auto [u,v]:edges) {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void Solve(int _N) {
N=_N;
vis[0]=true;
for(int i=1;i<N;i++) {
if(vis[i]) continue;
// cout<<"try : "<<i<<endl;
// for(auto [u,v]:edges) {
// cout<<u<<" "<<v<<endl;
// }
prep();
cdc(0,i);
}
for(auto [u,v]:edges) {
if(u>v) swap(u,v);
Bridge(u,v);
}
}
Compilation message
meetings.cpp: In function 'void cdc(int, int)':
meetings.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i=0;i<conds.size();i+=2) {
| ~^~~~~~~~~~~~~
meetings.cpp:71:37: warning: unused variable 'k' [-Wunused-variable]
71 | int k=u;
| ^
meetings.cpp:78:37: warning: unused variable 'k' [-Wunused-variable]
78 | int k=v;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
524 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
524 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 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 |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
524 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
0 ms |
344 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
344 KB |
Output is correct |
16 |
Correct |
1 ms |
344 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
1 ms |
344 KB |
Output is correct |
19 |
Correct |
1 ms |
344 KB |
Output is correct |
20 |
Correct |
1 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
344 KB |
Output is correct |
25 |
Correct |
1 ms |
344 KB |
Output is correct |
26 |
Correct |
1 ms |
344 KB |
Output is correct |
27 |
Correct |
6 ms |
600 KB |
Output is correct |
28 |
Correct |
7 ms |
600 KB |
Output is correct |
29 |
Correct |
6 ms |
600 KB |
Output is correct |
30 |
Correct |
6 ms |
600 KB |
Output is correct |
31 |
Correct |
8 ms |
600 KB |
Output is correct |
32 |
Correct |
5 ms |
600 KB |
Output is correct |
33 |
Correct |
8 ms |
592 KB |
Output is correct |
34 |
Correct |
7 ms |
600 KB |
Output is correct |
35 |
Correct |
7 ms |
600 KB |
Output is correct |
36 |
Correct |
6 ms |
600 KB |
Output is correct |
37 |
Correct |
8 ms |
600 KB |
Output is correct |
38 |
Correct |
11 ms |
600 KB |
Output is correct |
39 |
Correct |
7 ms |
600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
472 ms |
1936 KB |
Output is correct |
2 |
Correct |
448 ms |
2128 KB |
Output is correct |
3 |
Correct |
414 ms |
1980 KB |
Output is correct |
4 |
Correct |
431 ms |
1956 KB |
Output is correct |
5 |
Correct |
311 ms |
1624 KB |
Output is correct |
6 |
Correct |
258 ms |
1680 KB |
Output is correct |
7 |
Correct |
321 ms |
2020 KB |
Output is correct |
8 |
Correct |
374 ms |
2308 KB |
Output is correct |
9 |
Correct |
341 ms |
2132 KB |
Output is correct |
10 |
Correct |
357 ms |
2344 KB |
Output is correct |
11 |
Correct |
431 ms |
2384 KB |
Output is correct |
12 |
Correct |
461 ms |
1956 KB |
Output is correct |
13 |
Correct |
458 ms |
2372 KB |
Output is correct |
14 |
Correct |
717 ms |
3444 KB |
Output is correct |
15 |
Correct |
683 ms |
3540 KB |
Output is correct |
16 |
Correct |
753 ms |
3916 KB |
Output is correct |
17 |
Correct |
324 ms |
2032 KB |
Output is correct |
18 |
Correct |
1448 ms |
6936 KB |
Output is correct |
19 |
Correct |
1400 ms |
6868 KB |
Output is correct |
20 |
Correct |
798 ms |
4108 KB |
Output is correct |
21 |
Correct |
786 ms |
3608 KB |
Output is correct |
22 |
Correct |
724 ms |
3560 KB |
Output is correct |
23 |
Correct |
714 ms |
3532 KB |
Output is correct |
24 |
Correct |
725 ms |
3640 KB |
Output is correct |
25 |
Correct |
1347 ms |
6832 KB |
Output is correct |
26 |
Correct |
1438 ms |
6820 KB |
Output is correct |
27 |
Correct |
1314 ms |
6792 KB |
Output is correct |
28 |
Correct |
454 ms |
2780 KB |
Output is correct |
29 |
Correct |
332 ms |
2192 KB |
Output is correct |
30 |
Correct |
388 ms |
2600 KB |
Output is correct |
31 |
Correct |
431 ms |
2360 KB |
Output is correct |
32 |
Correct |
590 ms |
1984 KB |
Output is correct |
33 |
Correct |
413 ms |
2120 KB |
Output is correct |
34 |
Correct |
6 ms |
600 KB |
Output is correct |
35 |
Correct |
6 ms |
600 KB |
Output is correct |
36 |
Correct |
6 ms |
600 KB |
Output is correct |
37 |
Correct |
6 ms |
600 KB |
Output is correct |
38 |
Correct |
5 ms |
600 KB |
Output is correct |
39 |
Correct |
5 ms |
600 KB |
Output is correct |
40 |
Correct |
6 ms |
600 KB |
Output is correct |
41 |
Correct |
9 ms |
600 KB |
Output is correct |
42 |
Correct |
10 ms |
744 KB |
Output is correct |
43 |
Correct |
5 ms |
600 KB |
Output is correct |
44 |
Correct |
8 ms |
708 KB |
Output is correct |
45 |
Correct |
9 ms |
600 KB |
Output is correct |
46 |
Correct |
8 ms |
924 KB |
Output is correct |
47 |
Correct |
1 ms |
344 KB |
Output is correct |
48 |
Correct |
1 ms |
344 KB |
Output is correct |
49 |
Correct |
1 ms |
344 KB |
Output is correct |
50 |
Correct |
1 ms |
344 KB |
Output is correct |
51 |
Correct |
1 ms |
344 KB |
Output is correct |
52 |
Correct |
1 ms |
340 KB |
Output is correct |
53 |
Correct |
1 ms |
344 KB |
Output is correct |
54 |
Correct |
1 ms |
344 KB |
Output is correct |
55 |
Correct |
1 ms |
344 KB |
Output is correct |
56 |
Correct |
1 ms |
344 KB |
Output is correct |
57 |
Correct |
1 ms |
344 KB |
Output is correct |
58 |
Correct |
1 ms |
344 KB |
Output is correct |
59 |
Correct |
1 ms |
556 KB |
Output is correct |
60 |
Correct |
0 ms |
344 KB |
Output is correct |
61 |
Correct |
0 ms |
344 KB |
Output is correct |
62 |
Correct |
0 ms |
344 KB |
Output is correct |
63 |
Correct |
0 ms |
344 KB |
Output is correct |
64 |
Correct |
0 ms |
344 KB |
Output is correct |
65 |
Correct |
0 ms |
344 KB |
Output is correct |
66 |
Correct |
0 ms |
344 KB |
Output is correct |
67 |
Correct |
0 ms |
344 KB |
Output is correct |
68 |
Correct |
0 ms |
344 KB |
Output is correct |
69 |
Correct |
0 ms |
344 KB |
Output is correct |
70 |
Correct |
0 ms |
344 KB |
Output is correct |
71 |
Correct |
0 ms |
344 KB |
Output is correct |
72 |
Correct |
0 ms |
344 KB |
Output is correct |