제출 #522250

#제출 시각아이디문제언어결과실행 시간메모리
522250phamhoanghiepMeetings (JOI19_meetings)C++14
0 / 100
56 ms696 KiB
#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++) { do_things(subtree[i]); } } void Solve(int N) { for(int i=0 ; i<N ; i++) vt.push_back(i); do_things(vt); for(ii tmp: edges) { Bridge(tmp.first,tmp.second); } // base 0 } /* signed main() { cin>>N; Solve(N); } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...