#include<bits/stdc++.h>
#include"meetings.h"
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
map<iii,int> M;
mt19937 rng(1);
int Rand(int l, int r) {
return rng()%(r-l+1)+l;
}
const int maxn=100005;
vector<int> vt;
vector<ii> edges;
vector<int> path;
vector<int> subtree[maxn];
int belong[maxn];
int _N;
int st=0;
/*
int Query(int u, int v, int w) {
cout<<"query "<<u<<" "<<v<<" "<<w<<endl;
int x;
cin>>x;
return x;
}
void Bridge(int u, int v) {
cout<<"edge "<<u<<" "<<v<<endl;
}
*/
int ask(int u, int v, int w) {
if(v>w) swap(v,w);
if(u>v) swap(u,v);
if(v>w) swap(v,w);
if(M[iii(u,ii(v,w))]) return M[iii(u,ii(v,w))];
else return M[iii(u,ii(v,w))]=Query(u,v,w);
}
void push(vector<int>& vec, int pos, int val) {
// right before pos (between pos and pos-1)
//cout<<"push "<<pos<<" "<<val<<endl;
vector<int> nw;
for(int i=0 ; i<(int)vec.size() ; i++) {
if(i==pos) nw.push_back(val);
nw.push_back(vec[i]);
}
vec.swap(nw);
}
void do_path() {
//cout<<"path: "<<endl;
//for(int u: path) cout<<u<<' ';
//cout<<endl;
vector<int> res;
res.push_back(path[0]);
res.push_back(path[1]);
for(int i=2 ; i<(int)path.size() ; i++) {
// find for path(i), current inside res: i
if(ask(res[0],res[1],path[i])==res[0]) push(res,0,path[i]);
else if(ask(res[i-1],res[i-2],path[i])==res[i-1]) res.push_back(path[i]);
else {
int l=0;
int r=i-2;
while(l<r) {
//cout<<"l r "<<l<<" "<<r<<endl;
int mid=(l+r+1)/2;
if(ask(res[mid],res[mid+1],path[i])==res[mid]) r=mid-1;
else l=mid;
}
//cout<<"l = "<<l<<endl;
push(res,l+1,path[i]);
}
//cout<<"res: "<<endl;
//for(int u: res) cout<<u<<' ';
//cout<<endl;
}
//cout<<"res: "<<endl;
//for(int u: res) cout<<u<<' ';
//cout<<endl;
for(int i=0 ; i<(int)res.size()-1 ; i++) {
edges.push_back(ii(res[i],res[i+1]));
}
}
void do_things(vector<int> &nodes) {
//cout<<"nodes: "<<endl;
//for(int u: nodes) cout<<u<<' ';
//cout<<endl;
if(nodes.size()<2) {
return;
}
if(nodes.size()==2) {
edges.push_back(ii(nodes[0],nodes[1]));
return;
}
for(int i=0 ; i<_N ; i++) belong[i]=0;
path.clear();
int sz=nodes.size();
int root1=Rand(0,sz-1);
int root2=Rand(0,sz-1);
while(root2==root1) root2=Rand(0,sz-1);
root1=nodes[root1]; root2=nodes[root2];
int stt=st+1;
belong[root1]=st+1;
belong[root2]=st+2;
subtree[st+1].push_back(root1);
//cout<<"subtree "<<st+1<<".push_back "<<root1<<endl;
subtree[st+2].push_back(root2);
//cout<<"subtree "<<st+2<<".push_back "<<root2<<endl;
st+=2;
path.push_back(root1); path.push_back(root2);
for(int u: nodes) {
if(u==root1||u==root2) continue;
int x=ask(root1,root2,u);
if(!belong[x]) {
belong[x]=++st;
path.push_back(x);
}
subtree[belong[x]].push_back(u);
//cout<<"subtree "<<belong[x]<<".push_back "<<u<<endl;
}
int en=st;
sort(path.begin(),path.end());
auto it=unique(path.begin(),path.end());
path.resize(distance(path.begin(),it));
do_path();
for(int i=stt ; i<=en ; i++) {
sort(subtree[i].begin(),subtree[i].end());
auto it=unique(subtree[i].begin(),subtree[i].end());
subtree[i].resize(distance(subtree[i].begin(),it));
//cout<<"i = "<<i<<endl;
do_things(subtree[i]);
}
}
void Solve(int N) {
_N=N;
for(int i=0 ; i<N ; i++) vt.push_back(i);
do_things(vt);
for(int i=0 ; i<(int)edges.size() ; i++) {
if(edges[i].first>edges[i].second) swap(edges[i].first,edges[i].second);
}
sort(edges.begin(),edges.end());
for(int i=0 ; i<(int)edges.size() ; i++) {
//cout<<"edges "<<i<<" = "<<edges[i].first<<" "<<edges[i].second<<endl;
if(!i||edges[i]!=edges[i-1]) Bridge(edges[i].first,edges[i].second);
}
// base 0
}
/*
signed main() {
int N;
cin>>N;
Solve(N);
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2632 KB |
Output is correct |
2 |
Correct |
2 ms |
2632 KB |
Output is correct |
3 |
Correct |
2 ms |
2632 KB |
Output is correct |
4 |
Correct |
2 ms |
2632 KB |
Output is correct |
5 |
Correct |
2 ms |
2632 KB |
Output is correct |
6 |
Correct |
2 ms |
2632 KB |
Output is correct |
7 |
Correct |
1 ms |
2632 KB |
Output is correct |
8 |
Correct |
1 ms |
2632 KB |
Output is correct |
9 |
Correct |
2 ms |
2632 KB |
Output is correct |
10 |
Correct |
1 ms |
2632 KB |
Output is correct |
11 |
Correct |
1 ms |
2632 KB |
Output is correct |
12 |
Correct |
2 ms |
2632 KB |
Output is correct |
13 |
Correct |
2 ms |
2632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2632 KB |
Output is correct |
2 |
Correct |
2 ms |
2632 KB |
Output is correct |
3 |
Correct |
2 ms |
2632 KB |
Output is correct |
4 |
Correct |
2 ms |
2632 KB |
Output is correct |
5 |
Correct |
2 ms |
2632 KB |
Output is correct |
6 |
Correct |
2 ms |
2632 KB |
Output is correct |
7 |
Correct |
1 ms |
2632 KB |
Output is correct |
8 |
Correct |
1 ms |
2632 KB |
Output is correct |
9 |
Correct |
2 ms |
2632 KB |
Output is correct |
10 |
Correct |
1 ms |
2632 KB |
Output is correct |
11 |
Correct |
1 ms |
2632 KB |
Output is correct |
12 |
Correct |
2 ms |
2632 KB |
Output is correct |
13 |
Correct |
2 ms |
2632 KB |
Output is correct |
14 |
Correct |
2 ms |
2632 KB |
Output is correct |
15 |
Correct |
2 ms |
2632 KB |
Output is correct |
16 |
Correct |
2 ms |
2632 KB |
Output is correct |
17 |
Correct |
2 ms |
2704 KB |
Output is correct |
18 |
Correct |
2 ms |
2632 KB |
Output is correct |
19 |
Correct |
2 ms |
2632 KB |
Output is correct |
20 |
Correct |
2 ms |
2632 KB |
Output is correct |
21 |
Correct |
2 ms |
2632 KB |
Output is correct |
22 |
Correct |
2 ms |
2632 KB |
Output is correct |
23 |
Correct |
2 ms |
2632 KB |
Output is correct |
24 |
Correct |
2 ms |
2628 KB |
Output is correct |
25 |
Correct |
2 ms |
2632 KB |
Output is correct |
26 |
Correct |
2 ms |
2632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2632 KB |
Output is correct |
2 |
Correct |
2 ms |
2632 KB |
Output is correct |
3 |
Correct |
2 ms |
2632 KB |
Output is correct |
4 |
Correct |
2 ms |
2632 KB |
Output is correct |
5 |
Correct |
2 ms |
2632 KB |
Output is correct |
6 |
Correct |
2 ms |
2632 KB |
Output is correct |
7 |
Correct |
1 ms |
2632 KB |
Output is correct |
8 |
Correct |
1 ms |
2632 KB |
Output is correct |
9 |
Correct |
2 ms |
2632 KB |
Output is correct |
10 |
Correct |
1 ms |
2632 KB |
Output is correct |
11 |
Correct |
1 ms |
2632 KB |
Output is correct |
12 |
Correct |
2 ms |
2632 KB |
Output is correct |
13 |
Correct |
2 ms |
2632 KB |
Output is correct |
14 |
Correct |
2 ms |
2632 KB |
Output is correct |
15 |
Correct |
2 ms |
2632 KB |
Output is correct |
16 |
Correct |
2 ms |
2632 KB |
Output is correct |
17 |
Correct |
2 ms |
2704 KB |
Output is correct |
18 |
Correct |
2 ms |
2632 KB |
Output is correct |
19 |
Correct |
2 ms |
2632 KB |
Output is correct |
20 |
Correct |
2 ms |
2632 KB |
Output is correct |
21 |
Correct |
2 ms |
2632 KB |
Output is correct |
22 |
Correct |
2 ms |
2632 KB |
Output is correct |
23 |
Correct |
2 ms |
2632 KB |
Output is correct |
24 |
Correct |
2 ms |
2628 KB |
Output is correct |
25 |
Correct |
2 ms |
2632 KB |
Output is correct |
26 |
Correct |
2 ms |
2632 KB |
Output is correct |
27 |
Correct |
7 ms |
2760 KB |
Output is correct |
28 |
Correct |
6 ms |
2760 KB |
Output is correct |
29 |
Correct |
6 ms |
2760 KB |
Output is correct |
30 |
Correct |
7 ms |
2760 KB |
Output is correct |
31 |
Correct |
5 ms |
2760 KB |
Output is correct |
32 |
Correct |
6 ms |
2760 KB |
Output is correct |
33 |
Correct |
13 ms |
2888 KB |
Output is correct |
34 |
Correct |
9 ms |
2888 KB |
Output is correct |
35 |
Correct |
10 ms |
2896 KB |
Output is correct |
36 |
Correct |
5 ms |
2760 KB |
Output is correct |
37 |
Correct |
9 ms |
2888 KB |
Output is correct |
38 |
Correct |
10 ms |
2888 KB |
Output is correct |
39 |
Correct |
6 ms |
2760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
337 ms |
3868 KB |
Output is correct |
2 |
Correct |
322 ms |
3776 KB |
Output is correct |
3 |
Correct |
464 ms |
3992 KB |
Output is correct |
4 |
Correct |
396 ms |
3976 KB |
Output is correct |
5 |
Correct |
264 ms |
3756 KB |
Output is correct |
6 |
Correct |
245 ms |
3756 KB |
Output is correct |
7 |
Correct |
380 ms |
4360 KB |
Output is correct |
8 |
Correct |
343 ms |
4348 KB |
Output is correct |
9 |
Correct |
419 ms |
4752 KB |
Output is correct |
10 |
Correct |
359 ms |
4472 KB |
Output is correct |
11 |
Correct |
380 ms |
4520 KB |
Output is correct |
12 |
Correct |
347 ms |
3812 KB |
Output is correct |
13 |
Correct |
241 ms |
3792 KB |
Output is correct |
14 |
Correct |
252 ms |
3952 KB |
Output is correct |
15 |
Correct |
341 ms |
4136 KB |
Output is correct |
16 |
Correct |
264 ms |
3908 KB |
Output is correct |
17 |
Correct |
397 ms |
4544 KB |
Output is correct |
18 |
Correct |
219 ms |
3780 KB |
Output is correct |
19 |
Correct |
224 ms |
3736 KB |
Output is correct |
20 |
Correct |
361 ms |
4276 KB |
Output is correct |
21 |
Correct |
314 ms |
3944 KB |
Output is correct |
22 |
Correct |
331 ms |
3924 KB |
Output is correct |
23 |
Correct |
374 ms |
4000 KB |
Output is correct |
24 |
Correct |
276 ms |
3960 KB |
Output is correct |
25 |
Correct |
299 ms |
3872 KB |
Output is correct |
26 |
Correct |
275 ms |
3852 KB |
Output is correct |
27 |
Correct |
287 ms |
3700 KB |
Output is correct |
28 |
Correct |
461 ms |
4800 KB |
Output is correct |
29 |
Correct |
373 ms |
4436 KB |
Output is correct |
30 |
Correct |
343 ms |
4580 KB |
Output is correct |
31 |
Correct |
481 ms |
4452 KB |
Output is correct |
32 |
Correct |
671 ms |
4408 KB |
Output is correct |
33 |
Correct |
220 ms |
3552 KB |
Output is correct |
34 |
Correct |
7 ms |
2820 KB |
Output is correct |
35 |
Correct |
6 ms |
2788 KB |
Output is correct |
36 |
Correct |
5 ms |
2852 KB |
Output is correct |
37 |
Correct |
5 ms |
2760 KB |
Output is correct |
38 |
Correct |
7 ms |
2760 KB |
Output is correct |
39 |
Correct |
8 ms |
2760 KB |
Output is correct |
40 |
Correct |
12 ms |
2888 KB |
Output is correct |
41 |
Correct |
9 ms |
2856 KB |
Output is correct |
42 |
Correct |
10 ms |
2888 KB |
Output is correct |
43 |
Correct |
6 ms |
2760 KB |
Output is correct |
44 |
Correct |
9 ms |
2888 KB |
Output is correct |
45 |
Correct |
9 ms |
2804 KB |
Output is correct |
46 |
Correct |
6 ms |
2760 KB |
Output is correct |
47 |
Correct |
2 ms |
2632 KB |
Output is correct |
48 |
Correct |
2 ms |
2692 KB |
Output is correct |
49 |
Correct |
2 ms |
2632 KB |
Output is correct |
50 |
Correct |
2 ms |
2632 KB |
Output is correct |
51 |
Correct |
2 ms |
2632 KB |
Output is correct |
52 |
Correct |
2 ms |
2632 KB |
Output is correct |
53 |
Correct |
3 ms |
2632 KB |
Output is correct |
54 |
Correct |
3 ms |
2632 KB |
Output is correct |
55 |
Correct |
2 ms |
2632 KB |
Output is correct |
56 |
Correct |
2 ms |
2632 KB |
Output is correct |
57 |
Correct |
2 ms |
2632 KB |
Output is correct |
58 |
Correct |
2 ms |
2632 KB |
Output is correct |
59 |
Correct |
2 ms |
2632 KB |
Output is correct |
60 |
Correct |
2 ms |
2632 KB |
Output is correct |
61 |
Correct |
2 ms |
2632 KB |
Output is correct |
62 |
Correct |
2 ms |
2632 KB |
Output is correct |
63 |
Correct |
1 ms |
2632 KB |
Output is correct |
64 |
Correct |
3 ms |
2632 KB |
Output is correct |
65 |
Correct |
2 ms |
2632 KB |
Output is correct |
66 |
Correct |
2 ms |
2632 KB |
Output is correct |
67 |
Correct |
2 ms |
2632 KB |
Output is correct |
68 |
Correct |
2 ms |
2632 KB |
Output is correct |
69 |
Correct |
2 ms |
2632 KB |
Output is correct |
70 |
Correct |
2 ms |
2632 KB |
Output is correct |
71 |
Correct |
1 ms |
2632 KB |
Output is correct |
72 |
Correct |
1 ms |
2632 KB |
Output is correct |