#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=2005;
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)
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) {
int mid=(l+r+1)/2;
if(ask(res[l],res[l+1],path[i])==res[l]) r=mid-1;
else l=mid;
}
push(res,l+1,path[i]);
}
}
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;
}
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;
}
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<=st ; 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));
do_things(subtree[i]);
}
}
void Solve(int 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() {
cin>>N;
Solve(N);
}
*/
| # |
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 |
1 ms |
328 KB |
Output is correct |
| 5 |
Correct |
0 ms |
328 KB |
Output is correct |
| 6 |
Correct |
0 ms |
328 KB |
Output is correct |
| 7 |
Correct |
1 ms |
392 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
328 KB |
Wrong Answer [4] |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
328 KB |
Output is correct |
| 5 |
Correct |
0 ms |
328 KB |
Output is correct |
| 6 |
Correct |
0 ms |
328 KB |
Output is correct |
| 7 |
Correct |
1 ms |
392 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
328 KB |
Wrong Answer [4] |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
1 ms |
328 KB |
Output is correct |
| 5 |
Correct |
0 ms |
328 KB |
Output is correct |
| 6 |
Correct |
0 ms |
328 KB |
Output is correct |
| 7 |
Correct |
1 ms |
392 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
328 KB |
Wrong Answer [4] |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
596 KB |
Wrong Answer [1] |
| 2 |
Halted |
0 ms |
0 KB |
- |
