#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000+10,lg=11;
int n,par[maxn],vis[maxn],visc[maxn],sz[maxn];
vector<int>adj[maxn];
set<int>st[maxn];
void createt(int u){
for(int i=1;i<=n;i++){
adj[i].clear();
visc[i]=0;
for(auto x:st[i]){
adj[i].push_back(x);
}
}
}
void adde(int u,int v){
st[u].insert(v);
st[v].insert(u);
vis[u]=vis[v]=1;
return ;
}
void erasee(int u,int v){
st[u].erase(v);
st[v].erase(u);
return ;
}
void calsz(int u,int par=-1){
sz[u]=1;
for(auto x:adj[u]){
if(x!=par&&visc[x]==0){
calsz(x,u);
sz[u]+=sz[x];
}
}
}
int findc(int u,int mx,int par=-1){
for(auto x:adj[u]){
if(x!=par&&visc[x]==0&&sz[x]*2>mx){
return findc(x,mx,u);
}
}
return u;
}
void solve(int u,int val){
calsz(u);
int v=findc(u,sz[u]);
vector<int>tof;
for(auto x:adj[v]){
if(visc[x]==0){
tof.push_back(x);
}
}
visc[v]=1;
for(int i=0;i+1<(int)tof.size();i+=2){
//cout<<"nagoo"<<endl;
int rr=Query(tof[i]-1,tof[i+1]-1,val-1)+1;
//cout<<"raft"<<endl;
if(rr==v){
continue;
}
if(rr==tof[i]){
solve(tof[i],val);
return ;
}
if(rr==tof[i+1]){
solve(tof[i+1],val);
return ;
}
val=rr;
//cout<<"wtf"<<endl;
rr=Query(tof[i]-1,val-1,v-1)+1;
//cout<<"raft"<<endl;
if(rr==val){
erasee(tof[i],v);
adde(tof[i],val);
adde(val,v);
}
else{
erasee(tof[i+1],v);
adde(tof[i+1],val);
adde(val,v);
}
return ;
}
if((int)tof.size()%2==1){
int rr=Query(val-1,v-1,tof.back()-1)+1;
if(vis[rr]==0){
val=rr;
erasee(tof.back(),v);
adde(tof.back(),val);
adde(val,v);
return ;
}
if(rr==tof.back()){
solve(tof.back(),val);
return ;
}
}
adde(v,val);
return ;
}
void in(int u){
if(u==1){
vis[u]=1;
return ;
}
if(u==2){
vis[u]=1;
par[u]=1;
adde(1,2);
return ;
}
createt(u);
solve(1,u);
}
void Solve(int N){
n=N;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[j]==0){
in(j);
}
}
}
int ted=0;
for(int i=1;i<=n;i++){
for(auto x:st[i]){
if(x>i){
//cout<<x<<" "<<i<<endl;
ted++;
Bridge(i-1,x-1);
}
}
}
if(ted<=1){
assert(0);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
600 KB |
Output is correct |
5 |
Correct |
0 ms |
600 KB |
Output is correct |
6 |
Correct |
0 ms |
600 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
0 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
0 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
600 KB |
Output is correct |
5 |
Correct |
0 ms |
600 KB |
Output is correct |
6 |
Correct |
0 ms |
600 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
0 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
0 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
600 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
600 KB |
Output is correct |
21 |
Correct |
1 ms |
600 KB |
Output is correct |
22 |
Correct |
1 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
600 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
1 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
600 KB |
Output is correct |
3 |
Correct |
1 ms |
600 KB |
Output is correct |
4 |
Correct |
0 ms |
600 KB |
Output is correct |
5 |
Correct |
0 ms |
600 KB |
Output is correct |
6 |
Correct |
0 ms |
600 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
0 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
600 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
600 KB |
Output is correct |
12 |
Correct |
0 ms |
600 KB |
Output is correct |
13 |
Correct |
1 ms |
600 KB |
Output is correct |
14 |
Correct |
1 ms |
600 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
600 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
1 ms |
600 KB |
Output is correct |
20 |
Correct |
1 ms |
600 KB |
Output is correct |
21 |
Correct |
1 ms |
600 KB |
Output is correct |
22 |
Correct |
1 ms |
600 KB |
Output is correct |
23 |
Correct |
1 ms |
600 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
1 ms |
600 KB |
Output is correct |
26 |
Correct |
1 ms |
600 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 |
5 ms |
600 KB |
Output is correct |
31 |
Correct |
5 ms |
600 KB |
Output is correct |
32 |
Correct |
4 ms |
600 KB |
Output is correct |
33 |
Correct |
5 ms |
600 KB |
Output is correct |
34 |
Correct |
6 ms |
600 KB |
Output is correct |
35 |
Correct |
6 ms |
600 KB |
Output is correct |
36 |
Correct |
5 ms |
600 KB |
Output is correct |
37 |
Correct |
6 ms |
704 KB |
Output is correct |
38 |
Correct |
7 ms |
600 KB |
Output is correct |
39 |
Correct |
6 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
403 ms |
1112 KB |
Output is correct |
2 |
Correct |
464 ms |
1080 KB |
Output is correct |
3 |
Correct |
433 ms |
1100 KB |
Output is correct |
4 |
Correct |
423 ms |
1044 KB |
Output is correct |
5 |
Correct |
321 ms |
1068 KB |
Output is correct |
6 |
Correct |
251 ms |
980 KB |
Output is correct |
7 |
Correct |
324 ms |
1360 KB |
Output is correct |
8 |
Correct |
364 ms |
1000 KB |
Output is correct |
9 |
Correct |
335 ms |
1124 KB |
Output is correct |
10 |
Correct |
325 ms |
1060 KB |
Output is correct |
11 |
Correct |
400 ms |
1108 KB |
Output is correct |
12 |
Correct |
473 ms |
1104 KB |
Output is correct |
13 |
Correct |
412 ms |
1388 KB |
Output is correct |
14 |
Correct |
630 ms |
1304 KB |
Output is correct |
15 |
Correct |
607 ms |
1104 KB |
Output is correct |
16 |
Correct |
682 ms |
1356 KB |
Output is correct |
17 |
Correct |
299 ms |
1104 KB |
Output is correct |
18 |
Correct |
1234 ms |
1104 KB |
Output is correct |
19 |
Correct |
1268 ms |
1164 KB |
Output is correct |
20 |
Correct |
684 ms |
1104 KB |
Output is correct |
21 |
Correct |
697 ms |
1156 KB |
Output is correct |
22 |
Correct |
644 ms |
1228 KB |
Output is correct |
23 |
Correct |
591 ms |
1212 KB |
Output is correct |
24 |
Correct |
665 ms |
1100 KB |
Output is correct |
25 |
Correct |
1216 ms |
1272 KB |
Output is correct |
26 |
Correct |
1235 ms |
1188 KB |
Output is correct |
27 |
Correct |
1236 ms |
1280 KB |
Output is correct |
28 |
Correct |
451 ms |
1040 KB |
Output is correct |
29 |
Correct |
314 ms |
1236 KB |
Output is correct |
30 |
Correct |
358 ms |
1108 KB |
Output is correct |
31 |
Correct |
388 ms |
1100 KB |
Output is correct |
32 |
Correct |
470 ms |
1104 KB |
Output is correct |
33 |
Correct |
340 ms |
1280 KB |
Output is correct |
34 |
Correct |
5 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 |
5 ms |
600 KB |
Output is correct |
38 |
Correct |
5 ms |
600 KB |
Output is correct |
39 |
Correct |
4 ms |
600 KB |
Output is correct |
40 |
Correct |
6 ms |
600 KB |
Output is correct |
41 |
Correct |
7 ms |
600 KB |
Output is correct |
42 |
Correct |
6 ms |
600 KB |
Output is correct |
43 |
Correct |
7 ms |
600 KB |
Output is correct |
44 |
Correct |
6 ms |
600 KB |
Output is correct |
45 |
Correct |
7 ms |
600 KB |
Output is correct |
46 |
Correct |
6 ms |
600 KB |
Output is correct |
47 |
Correct |
1 ms |
600 KB |
Output is correct |
48 |
Correct |
1 ms |
600 KB |
Output is correct |
49 |
Correct |
1 ms |
600 KB |
Output is correct |
50 |
Correct |
1 ms |
600 KB |
Output is correct |
51 |
Correct |
1 ms |
600 KB |
Output is correct |
52 |
Correct |
1 ms |
600 KB |
Output is correct |
53 |
Correct |
1 ms |
600 KB |
Output is correct |
54 |
Correct |
1 ms |
600 KB |
Output is correct |
55 |
Correct |
1 ms |
600 KB |
Output is correct |
56 |
Correct |
1 ms |
600 KB |
Output is correct |
57 |
Correct |
1 ms |
600 KB |
Output is correct |
58 |
Correct |
1 ms |
600 KB |
Output is correct |
59 |
Correct |
1 ms |
600 KB |
Output is correct |
60 |
Correct |
0 ms |
600 KB |
Output is correct |
61 |
Correct |
0 ms |
600 KB |
Output is correct |
62 |
Correct |
1 ms |
600 KB |
Output is correct |
63 |
Correct |
0 ms |
600 KB |
Output is correct |
64 |
Correct |
1 ms |
600 KB |
Output is correct |
65 |
Correct |
0 ms |
600 KB |
Output is correct |
66 |
Correct |
1 ms |
600 KB |
Output is correct |
67 |
Correct |
0 ms |
600 KB |
Output is correct |
68 |
Correct |
0 ms |
600 KB |
Output is correct |
69 |
Correct |
0 ms |
600 KB |
Output is correct |
70 |
Correct |
0 ms |
600 KB |
Output is correct |
71 |
Correct |
0 ms |
596 KB |
Output is correct |
72 |
Correct |
1 ms |
600 KB |
Output is correct |