Submission #1078090

#TimeUsernameProblemLanguageResultExecution timeMemory
1078090noyancanturkSimurgh (IOI17_simurgh)C++17
0 / 100
1 ms348 KiB
#include "simurgh.h" #include<bits/stdc++.h> using namespace std; #define pb push_back const int lim=510; int n; int v[lim][lim]; int edgecnt[lim],p[lim]; struct{ int par[lim]; void init(){ for(int i=0;i<n;i++)par[i]=i; } int find(int i){ if(i==par[i])return i; return par[i]=find(par[i]); } void unite(int i,int j){ i=find(i),j=find(j); par[i]=j; } }dsu; void findedgecnt(int node){ vector<int>r; for(int i=0;i<n;i++){ if(i==node)continue; r.pb(v[node][i]); } edgecnt[node]=count_common_roads(r); if(node)edgecnt[node]--; } int lineadd(int node){ vector<int>r; for(int i=1;i+1<n;i++){ r.pb(v[i][i+1]); } r.pb(v[0][node]); return count_common_roads(r); } vector<int>legit; vector<int> find_roads(int N, vector<int> u1, vector<int> u2) { n=N; legit.clear(); for(int i=0;i<n;i++)p[i]=-1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) v[i][j]=-1; int m=u1.size(); for(int i=0;i<m;i++){ v[u1[i]][u2[i]]=i; v[u2[i]][u1[i]]=i; } if(m==n*(n-1)/2){ for(int i=0;i<n;i++)findedgecnt(i); int best=lineadd(1); vector<int>toad; toad.pb(1); for(int i=2;i<n;i++){ int cnt=lineadd(i); if(cnt==best){ toad.pb(i); }else if(best<cnt){ best=cnt; toad.clear(); toad.pb(i); } } vector<int>q; for(int i:toad){ q.pb(i); p[i]=0; legit.pb(v[0][i]); } while(q.size()){ int node=q.back(); q.pop_back(); vector<int>dudes; for(int i=1;i<n;i++){ if(p[i]==-1)dudes.pb(i); } int tt=-1; vector<int>found; while(edgecnt[node]){ int l=tt+2,r=dudes.size()-1,ans=tt+1; while(l<=r){ int mid=(l+r)>>1; vector<int>wow=legit; for(int i=0;i<mid;i++){ wow.pb(v[0][dudes[i]]); } for(int i=mid;i<dudes.size();i++){ wow.pb(v[node][dudes[i]]); } int cnt=count_common_roads(wow); if(cnt==edgecnt[node]){ ans=mid; l=mid+1; }else{ r=mid-1; } } found.pb(dudes[ans]); edgecnt[node]--; tt=ans; } for(int i:found){ p[i]=node; legit.pb(v[node][i]); q.pb(i); } } /* cerr<<"found :: "; for(int i:legit)cerr<<i<<" "; cerr<<"\n"; */ return legit; } return legit; /* vector<int> r(n - 1); for(int i = 0; i < n - 1; i++) r[i] = i; int common = count_common_roads(r); if(common == n - 1) return r; r[0] = n - 1; return r; */ }

Compilation message (stderr)

simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |      for(int i=mid;i<dudes.size();i++){
      |                    ~^~~~~~~~~~~~~
simurgh.cpp: At global scope:
simurgh.cpp:27:2: warning: 'dsu' defined but not used [-Wunused-variable]
   27 | }dsu;
      |  ^~~
#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...