Submission #400037

#TimeUsernameProblemLanguageResultExecution timeMemory
400037kshitij_sodaniSimurgh (IOI17_simurgh)C++14
70 / 100
312 ms5752 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second #define endl '\n' #define ask count_common_roads #include "simurgh.h" int par[501]; vector<pair<int,int>> adj[513]; int ind5[513][513]; int n; int vis[513]; int find(int no){ if(par[no]==no){ return no; } par[no]=find(par[no]); return par[no]; } int ca=-1; vector<int> pp; vector<int> pp2; void dfs(int no,int par2=-1){ if(no==ca){ pp2=pp; } for(auto j:adj[no]){ if(j.a!=par2){ pp.pb(j.b); dfs(j.a,no); pp.pop_back(); } } } vector<int> ans2; vector<int> ans; int ask2(vector<pair<int,int>> cur){ /*cout<<11<<endl; for(auto i:cur){ cout<<i.a<<"::"<<i.b<<endl; }*/ for(int i=0;i<n;i++){ vis[i]=0; } for(auto i:cur){ vis[i.a]=1; vis[i.b]=1; } /* for(auto i:cur){ cout<<i.a<<"::"<<i.b<<endl; }*/ vector<int> qq; int xx=0; for(int i=1;i<n;i++){ if(vis[i]==0){ qq.pb(ind5[0][i]); if(ans[ind5[0][i]]==1){ xx--; } } } for(auto i:cur){ qq.pb(ind5[i.a][i.b]); qq.pb(ind5[0][i.a]); if(ans[ind5[0][i.a]]==1){ xx--; } } /* for(auto j:qq){ cout<<j<<"."; } cout<<endl;*/ xx+=ask(qq); //cout<<xx<<endl<<endl; return xx; } void solve(vector<pair<int,int>> xx,int val2){ if(val2==0){ return; } if(xx.size()==1){ if(xx[0].b>xx[0].a+1 and xx[0].a!=0){ ans[ind5[xx[0].a][xx[0].b]]=1; ans2.pb(ind5[xx[0].a][xx[0].b]); } } else{ vector<pair<int,int>> yy; vector<pair<int,int>> zz; for(int i=0;i<xx.size()/2;i++){ yy.pb(xx[i]); } for(int i=xx.size()/2;i<xx.size();i++){ zz.pb(xx[i]); } int val3=ask2(yy); solve(yy,val3); solve(zz,val2-val3); } } vector<int> find_roads2(int n,vector<int> uu,vector<int> vv) { int m=uu.size(); for(int i=0;i<n;i++){ par[i]=i; } vector<pair<pair<int,int>,int>> cur; vector<pair<pair<int,int>,int>> cur2; for(int i=0;i<m;i++){ int x=find(uu[i]); int y=find(vv[i]); if(x!=y){ par[x]=y; cur.pb({{uu[i],vv[i]},i}); adj[uu[i]].pb({vv[i],i}); adj[vv[i]].pb({uu[i],i}); } else{ cur2.pb({{uu[i],vv[i]},i}); } } //mt19937 rng; //rng=mt19937(chrono::steady_clock::now().time_since_epoch().count()); int val; vector<int> ee; for(auto j:cur){ ee.pb(j.b); } val=ask(ee); vector<int> ans; for(int i=0;i<m;i++){ ans.pb(0); } for(auto j:cur2){ ca=j.a.b; dfs(j.a.a); int cur=-1; for(auto i:pp2){ if(ans[i]!=0){ cur=i; } } /* for(auto i:pp2){ cout<<i<<","; } cout<<endl;*/ if(cur==-1){ vector<pair<int,int>> xx; xx.pb({val,j.b}); for(auto i:pp2){ vector<int> ff; for(auto jj:ee){ if(jj!=i){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); xx.pb({val2,i}); } sort(xx.begin(),xx.end()); for(int i=0;i<xx.size();i++){ if(xx[i].a==xx.back().a-1){ ans[xx[i].b]=1; } else{ ans[xx[i].b]=-1; } } /*for(auto j:xx){ cout<<j.a<<"::"<<j.b<<endl; } cout<<endl;*/ } else{ if(true){ vector<int> ff; for(auto jj:ee){ if(jj!=cur){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); int xx=val; if(ans[cur]==1){ xx--; } if(val2==xx){ ans[j.b]=-1; } else{ ans[j.b]=1; } } for(auto i:pp2){ if(ans[i]!=0){ continue; } vector<int> ff; for(auto jj:ee){ if(jj!=i){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); int xx=val; if(ans[j.b]==1){ xx+=1; } if(val2==xx){ ans[i]=-1; } else{ ans[i]=1; } } } /* for(auto i:ans){ cout<<i<<"."; } cout<<endl;*/ } vector<int> ans2; for(int i=0;i<m;i++){ if(ans[i]==1 or ans[i]==0){ ans2.pb(i); } } // for(int i=0;i<m;i++){ // cout<<ans[i]<<":"; // } // cout<<endl; return ans2; /* shuffle(cur2.begin(),cur2.end(),rng); for(auto j:cur2){ if(val==n-1){ break; } for(int i=0;i<n;i++){ adj[i].clear(); } for(auto i:cur){ adj[i.a.a].pb({i.a.b,i.b}); adj[i.a.b].pb({i.a.a,i.b}); } ca=j.a.b; dfs(j.a.a); shuffle(pp2.begin(),pp2.end(),rng); for(auto i:pp2){ vector<int> ff; for(auto jj:ee){ if(jj!=i){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); if(val2<val){ break; } if(val2==val){ continue; } vector<pair<pair<int,int>,int>> cur3; for(auto ii:cur){ if(ii.b==i){ continue; } cur3.pb(ii); } cur3.pb(j); cur=cur3; val=val2; ee=ff; break; } }*/ // return ee; } vector<int> find_roads(int nnn,vector<int> uu,vector<int> vv) { int m=uu.size(); n=nnn; if(nnn<=240){ return find_roads2(n,uu,vv); } for(int i=0;i<n;i++){ par[i]=i; } vector<pair<pair<int,int>,int>> cur; vector<pair<pair<int,int>,int>> cur2; for(int i=0;i<m;i++){ if(uu[i]>vv[i]){ swap(uu[i],vv[i]); } ind5[uu[i]][vv[i]]=i; int x=find(uu[i]); int y=find(vv[i]); if(uu[i]!=0){ if(abs(uu[i]-vv[i])>1){ continue; } } if(uu[i]==0){ //par[x]=y; cur.pb({{uu[i],vv[i]},i}); adj[uu[i]].pb({vv[i],i}); adj[vv[i]].pb({uu[i],i}); } else{ cur2.pb({{uu[i],vv[i]},i}); } } //mt19937 rng; //rng=mt19937(chrono::steady_clock::now().time_since_epoch().count()); int val; vector<int> ee; for(auto j:cur){ ee.pb(j.b); } val=ask(ee); for(int i=0;i<m;i++){ if(uu[i]!=0){ if(abs(uu[i]-vv[i])>1){ ans.pb(-2); continue; } } ans.pb(0); } for(auto j:cur2){ ca=j.a.b; dfs(j.a.a); int cur=-1; for(auto i:pp2){ if(ans[i]!=0){ cur=i; } } /* for(auto i:pp2){ cout<<i<<","; } cout<<endl;*/ if(cur==-1){ vector<pair<int,int>> xx; xx.pb({val,j.b}); for(auto i:pp2){ vector<int> ff; for(auto jj:ee){ if(jj!=i){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); xx.pb({val2,i}); } sort(xx.begin(),xx.end()); for(int i=0;i<xx.size();i++){ if(xx[i].a==xx.back().a-1){ ans[xx[i].b]=1; } else{ ans[xx[i].b]=-1; } } /*for(auto j:xx){ cout<<j.a<<"::"<<j.b<<endl; } cout<<endl;*/ } else{ if(true){ vector<int> ff; for(auto jj:ee){ if(jj!=cur){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); int xx=val; if(ans[cur]==1){ xx--; } if(val2==xx){ ans[j.b]=-1; } else{ ans[j.b]=1; } } for(auto i:pp2){ if(ans[i]!=0){ continue; } vector<int> ff; for(auto jj:ee){ if(jj!=i){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); int xx=val; if(ans[j.b]==1){ xx+=1; } if(val2==xx){ ans[i]=-1; } else{ ans[i]=1; } } } /* for(auto i:ans){ cout<<i<<"."; } cout<<endl;*/ } vector<vector<pair<int,int>>> qq; for(int i=2;i<=256;i*=2){ vector<vector<int>> aa; vector<vector<int>> bb; for(int j=0;j<512;j+=i){ vector<int> cc; for(int k=j;k<j+i;k++){ cc.pb(k); } if((j/i)%2==0){ aa.pb(cc); } else{ bb.pb(cc); } } for(int j=0;j<i;j++){ for(int k=0;k<bb.size();k++){ vector<int> dd; for(int ii=1;ii<i;ii++){ dd.pb(bb[k][ii]); } dd.pb(bb[k][0]); bb[k]=dd; } vector<pair<int,int>> rr; for(int k=0;k<aa.size();k++){ for(int l=0;l<aa[k].size();l++){ rr.pb({aa[k][l],bb[k][l]}); } } qq.pb(rr); } } for(int i=0;i<m;i++){ if(ans[i]==0){ ans[i]=1; } if(ans[i]==1){ ans2.pb(i); } /*if(ans[i]==1 or ans[i]==0){ ans2.pb(i); }*/ //cout<<ans[i]<<":"; } //cout<<endl; for(auto j:qq){ vector<pair<int,int>> cur; for(auto i:j){ if(i.a<n and i.b<n and i.a!=0 and abs(i.b-i.a)!=1){ cur.pb(i); } } if(cur.size()){ /*for(int i=0;i<n;i++){ vis[i]=0; } for(auto i:cur){ vis[i.a]=1; vis[i.b]=1; }*/ /*for(auto i:cur){ cout<<i.a<<"::"<<i.b<<endl; } cout<<endl;*/ // cout<<ask2(cur)<<endl; solve(cur,ask2(cur)); } } // cout<<endl; // for(int i=0;i<m;i++){ // cout<<ans[i]<<":"; // } // cout<<endl; return ans2; /* shuffle(cur2.begin(),cur2.end(),rng); for(auto j:cur2){ if(val==n-1){ break; } for(int i=0;i<n;i++){ adj[i].clear(); } for(auto i:cur){ adj[i.a.a].pb({i.a.b,i.b}); adj[i.a.b].pb({i.a.a,i.b}); } ca=j.a.b; dfs(j.a.a); shuffle(pp2.begin(),pp2.end(),rng); for(auto i:pp2){ vector<int> ff; for(auto jj:ee){ if(jj!=i){ ff.pb(jj); } } ff.pb(j.b); int val2=ask(ff); if(val2<val){ break; } if(val2==val){ continue; } vector<pair<pair<int,int>,int>> cur3; for(auto ii:cur){ if(ii.b==i){ continue; } cur3.pb(ii); } cur3.pb(j); cur=cur3; val=val2; ee=ff; break; } }*/ // return ee; }

Compilation message (stderr)

simurgh.cpp: In function 'void solve(std::vector<std::pair<int, int> >, int)':
simurgh.cpp:98:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int i=0;i<xx.size()/2;i++){
      |               ~^~~~~~~~~~~~
simurgh.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int i=xx.size()/2;i<xx.size();i++){
      |                         ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads2(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:171:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |    for(int i=0;i<xx.size();i++){
      |                ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:311:7: warning: unused variable 'x' [-Wunused-variable]
  311 |   int x=find(uu[i]);
      |       ^
simurgh.cpp:312:7: warning: unused variable 'y' [-Wunused-variable]
  312 |   int y=find(vv[i]);
      |       ^
simurgh.cpp:376:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  376 |    for(int i=0;i<xx.size();i++){
      |                ~^~~~~~~~~~
simurgh.cpp:457:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  457 |    for(int k=0;k<bb.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:466:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  466 |    for(int k=0;k<aa.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:467:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  467 |     for(int l=0;l<aa[k].size();l++){
      |                 ~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...