Submission #1206455

#TimeUsernameProblemLanguageResultExecution timeMemory
1206455Aviansh도시들 (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 dist[110][110]; int getDist(int i, int j){ if(dist[i][j]==-1){ dist[i][j]=getDistance(i,j); } return dist[i][j]; } int hubDistance(int n, int sub) { for(int i = 0;i<n;i++){ for(int j = 0;j<n;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]; map<int,vector<int>>mp; int rds[n]; int cds[n]; 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; cds[i]=cd; 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(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...