Submission #400056

#TimeUsernameProblemLanguageResultExecution timeMemory
400056kshitij_sodaniSimurgh (IOI17_simurgh)C++14
51 / 100
3060 ms8448 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 ask3 //#define ask3 #include "simurgh.h" int par[513]; int par2[513]; int count3=0; int tt[500*500]; int ask3(vector<int> xx){ count3++; return count_common_roads(xx); } vector<pair<int,int>> adj[513]; int ind5[513][513]; int n; int vis[513]; vector<int> uu; vector<int> vv; int act[513*513]; int find(int no){ if(par[no]==no){ return no; } par[no]=find(par[no]); return par[no]; } int find2(int no){ if(par2[no]==no){ return no; } par2[no]=find2(par2[no]); return par2[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 and act[j.b]){ pp.pb(j.b); dfs(j.a,no); pp.pop_back(); } } } vector<int> ans2; vector<int> ans; int count2=0; vector<int> zz5; int ask2(vector<pair<int,int>> cur){ for(int i=0;i<n;i++){ adj[i].clear(); } for(auto i:zz5){ if(tt[i]==0){ adj[uu[i]].pb({vv[i],i}); adj[vv[i]].pb({uu[i],i}); act[i]=1; } } for(auto j:cur){ act[ind5[j.a][j.b]]=0; adj[j.a].pb({j.b,ind5[j.a][j.b]}); adj[j.b].pb({j.a,ind5[j.a][j.b]}); } for(auto j:cur){ ca=j.b; dfs(j.a); for(auto i:pp2){ if(tt[i]==0){ act[i]=0; act[ind5[j.a][j.b]]=1; vector<int> ff={uu[i],vv[i]}; /* for(auto ii:ff){ //if(uu[i]==ii or vv[i]==ii){ vector<pair<int,int>> ne; for(auto jj:adj[ii]){ if(jj.b!=i){ ne.pb(jj); } } adj[ii]=ne; //} }*/ //adj[j.a].pb({j.b,ind5[j.a][j.b]}); //adj[j.b].pb({j.a,ind5[j.a][j.b]}); break; } } } vector<int> qq; for(int i=0;i<n;i++){ for(auto j:adj[i]){ if(j.a>i and act[j.b]){ qq.pb(j.b); } } } /*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; }*/ int xx=0; /*for(int i=1;i<n;i++){ if(vis[i]==0){ qq.pb(ind5[0][i]); } } for(auto i:cur){ qq.pb(ind5[i.a][i.b]); qq.pb(ind5[0][i.a]); }*/ for(auto j:qq){ if(tt[j]==0){ if(ans[j]==1){ xx--; //cout<<j<<"<<"<<endl; } } } /*cout<<xx<<endl; for(auto j:qq){ cout<<j<<"."; } cout<<endl;*/ xx+=ask(qq); count2++; /*cout<<xx<<endl; cout<<endl;*/ //cout<<xx<<endl<<endl; return xx; } void solve(vector<pair<int,int>> xx,int val2){ if(val2==0){ return; } if(xx.size()==1){ //f(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_roads(int nnn,vector<int> uuu,vector<int> vvv) { uu=uuu; vv=vvv; int m=uu.size(); n=nnn; /*if(nnn<=240){ return find_roads2(n,uu,vv); }*/ count3=0; count2=0; for(int i=0;i<n;i++){ par[i]=i; par2[i]=i; } vector<pair<pair<int,int>,int>> cur; vector<pair<pair<int,int>,int>> cur2; vector<pair<pair<int,int>,int>> cur3; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ind5[i][j]=-1; } } for(int i=0;i<m;i++){ ans.pb(0); } 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(x!=y){ par[x]=y; tt[i]=0; zz5.pb(i); cur.pb({{uu[i],vv[i]},i}); adj[uu[i]].pb({vv[i],i}); adj[vv[i]].pb({uu[i],i}); } else{ x=find2(uu[i]); y=find2(vv[i]); if(x!=y){ tt[i]=1; par2[x]=y; cur2.pb({{uu[i],vv[i]},i}); } else{ tt[i]=2; cur3.pb({{uu[i],vv[i]},i}); ans[i]=-2; } } } //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); count2++; /*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(int i=0;i<m;i++){ act[i]=1; } 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); count2++; 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); count2++; 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); count2++; 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;*/ } for(int i=0;i<m;i++){ act[i]=0; } vector<vector<pair<int,int>>> qq; for(int i=1;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); } //cout<<ans[i]<<":"; } //cout<<endl; //cout<<cur3.size()<<endl; for(auto j:qq){ vector<pair<int,int>> cur; for(auto i:j){ if(i.a<n and i.b<n){ /*if(i.a==2 and i.b==3){ cout<<11<<endl; }*/ if(ind5[i.a][i.b]!=-1){ if(ans[ind5[i.a][i.b]]==-2){ cur.pb(i); } } } } if(cur.size()){ /* for(auto i:cur){ cout<<i.a<<"::"<<i.b<<endl; } cout<<endl;*/ solve(cur,ask2(cur)); } } /* for(int i=0;i<m;i++){ cout<<ans[i]<<":"; } cout<<endl; */ assert(count3<=8000); //cout<<count3<<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:179: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]
  179 |   for(int i=0;i<xx.size()/2;i++){
      |               ~^~~~~~~~~~~~
simurgh.cpp:182: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]
  182 |   for(int i=xx.size()/2;i<xx.size();i++){
      |                         ~^~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:305: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]
  305 |    for(int i=0;i<xx.size();i++){
      |                ~^~~~~~~~~~
simurgh.cpp:391:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  391 |    for(int k=0;k<bb.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:400:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  400 |    for(int k=0;k<aa.size();k++){
      |                ~^~~~~~~~~~
simurgh.cpp:401:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  401 |     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...