Submission #1076189

#TimeUsernameProblemLanguageResultExecution timeMemory
1076189AbitoSimurgh (IOI17_simurgh)C++17
30 / 100
2047 ms31932 KiB
#include "simurgh.h" #include <bits/stdc++.h> #define pb push_back #define ask count_common_roads using namespace std; const int N=4e4+5; int par[N],sz[N]; bool in[N],know[N]; map<vector<int>,int> mp; int getpar(int x){ if (x==par[x]) return x; return par[x]=getpar(par[x]); } bool link(int x,int y){ x=getpar(x); y=getpar(y); if (x==y) return 0; if (sz[x]>sz[y]) swap(x,y); sz[y]+=sz[x]; par[x]=y; return 1; } std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) { int m=u.size(); for (int i=0;i<m;i++) u[i]++,v[i]++; for (int i=1;i<=n;i++) sz[i]=1,par[i]=i; vector<int> r; for (int i=0;i<m;i++){ if (link(u[i],v[i])) r.pb(i),in[i]=1; } int ans=mp[r]=ask(r),q=1; for (int i=0;i<m && ans<n-1;i++){ if (!in[i] || know[i]) continue; int s=i; for (int j=0;j<m;j++){ if (in[j] || know[j]) continue; vector<int> t; for (auto x:r) if (x!=i) t.pb(x); t.pb(j); for (int i=1;i<=n;i++) sz[i]=1,par[i]=i; int tree=0; for (auto x:t) tree+=link(u[x],v[x]); if (tree!=n-1) continue; sort(t.begin(),t.end()); int h; if (mp.find(t)==mp.end()){ assert(q<30000); mp[t]=ask(t); } h=mp[t]; if (h<=ans) continue; s=j; in[s]=1; in[i]=0; swap(r,t); ans=h; break; } know[i]=1; know[s]=1; } return r; }
#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...