Submission #1206475

#TimeUsernameProblemLanguageResultExecution timeMemory
1206475AvianshTowns (IOI15_towns)C++20
38 / 100
11 ms516 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 dist[115][115]; int getDist(int i, int j){ if(dist[i][j]==-1){ dist[i][j]=getDistance(i,j); dist[j][i]=dist[i][j]; } return dist[i][j]; } int hubDistance(int n, int sub) { for(int i = 0;i<115;i++){ for(int j = 0;j<115;j++){ dist[i][j]=-1; } dist[i][i]=0; } int dists[n]; dists[0]=0; for(int i = 1;i<n;i++){ dists[i] = getDist(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]=getDist(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 = getDist(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); } if(sub<=2) return ans; 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(ds.findRoot(i)!=ds.findRoot(j)&&getDist(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...