Submission #1206461

#TimeUsernameProblemLanguageResultExecution timeMemory
1206461AvianshTowns (IOI15_towns)C++20
0 / 100
0 ms328 KiB
#include "towns.h" #include <bits/stdc++.h> using namespace std; struct dsu{ vector<int>root; vector<int>siz; int mxsiz=1; dsu(int n){ root=vector<int>(n); iota(root.begin(),root.end(),0); siz=vector<int>(n,1); } int findRoot(int x){ if(x==root[x]) return x; return root[x]=findRoot(root[x]); } bool unite(int x, int y){ x=findRoot(x); y=findRoot(y); if(x==y) return 0; if(siz[x]<siz[y]) swap(x,y); siz[x]+=siz[y]; root[y]=x; mxsiz=max(mxsiz,siz[x]); return 1; } }; int hubDistance(int n, int sub) { int dists[n]; dists[0]=0; for(int i = 1;i<n;i++){ dists[i] = getDistance(0,i); } int u = max_element(dists,dists+n)-dists; dists[u]=0; for(int i = 0;i<n;i++){ if(i==u) continue; dists[i]=getDistance(u,i); } int v = max_element(dists,dists+n)-dists; int ans = dists[v]; int rds[n]; map<int,vector<int>>mp; for(int i = 0;i<n;i++){ int d = getDistance(i,v); int cd = (dists[i]+dists[v]-d)/2; int rd = (dists[i]+d-dists[v])/2; rds[i]=rd; mp[cd].push_back(i); cd=max(cd,dists[v]-cd); ans=min(ans,cd); } bool wor = 0; int beh = 0; for(pair<int,vector<int>>p:mp){ if(p.first==ans||p.first==dists[v]-ans){ if(beh<=n/2&&(n-beh-p.second.size())<=n/2){ dsu ds(n); for(int i : p.second){ for(int j : p.second){ if(j<=i) continue; if(getDistance(i,j)<rds[i]+rds[j]){ ds.unite(i,j); } } } if(ds.mxsiz<=n/2){ wor=1; break; } } } beh+=p.second.size(); } if(!wor) ans=-ans; return ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...