| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 670268 | victor_gao | Towns (IOI15_towns) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towns.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include "graderlib.c"
#include <bits/stdc++.h>
#define MAXN 250
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int dis[MAXN][MAXN],cnt=1,go_fa[MAXN],fa[MAXN],son[MAXN],mxson[MAXN];
vector<pii>g[MAXN];
struct dsu{
int boss[MAXN+5];
void init(int n){
for (int i=1;i<=n;i++)
boss[i]=i;
}
int find(int x){
if (boss[x]==x) return x;
return boss[x]=find(boss[x]);
}
void Merge(int a,int b){
boss[find(a)]=boss[find(b)];
}
}d;
vector<int> solve(vector<int>have){
int n=have.size();
vector<int>all[n+5];
if (have.size()==1) return {};
else if (have.size()==2){
fa[have[0]]=have[1]; go_fa[have[0]]=dis[have[0]][have[1]];
fa[have[1]]=have[0]; go_fa[have[1]]=dis[have[0]][have[1]];
g[have[0]].push_back({have[1],dis[have[0]][have[1]]});
g[have[1]].push_back({have[0],dis[have[1]][have[0]]});
return {};
}
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
for (int k=j+1;k<n;k++){
if (i!=j&&k!=i&&j!=k){
int a=have[i],b=have[j],c=have[k];
all[i].push_back((dis[a][b]+dis[a][c]-dis[b][c])/2);
}
}
}
sort(all[i].begin(),all[i].end());
go_fa[have[i]]=all[i][0];
}
for (int i=0;i<n;i++){
for (int j=i+1;j<n;j++){
int a=have[i],b=have[j];
if (dis[a][b]==go_fa[a]+go_fa[b])
d.Merge(a,b);
}
}
vector<int>vt,ans;
for (int i=0;i<n;i++)
vt.push_back(d.find(have[i]));
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
for (auto i:vt)
fa[i]=cnt++;
for (int i=0;i<(int)vt.size();i++){
g[vt[i]].push_back({fa[vt[i]],go_fa[vt[i]]});
g[fa[vt[i]]].push_back({vt[i],go_fa[vt[i]]});
for (int j=i+1;j<(int)vt.size();j++){
int a=vt[i],b=vt[j];
int nd=dis[a][b]-go_fa[a]-go_fa[b];
dis[fa[a]][fa[b]]=nd;
dis[fa[b]][fa[a]]=nd;
}
}
for (auto i:have){
fa[i]=fa[d.find(i)];
g[i].push_back({fa[i],go_fa[i]});
g[fa[i]].push_back({i,go_fa[i]});
}
for (auto i:vt)
ans.push_back(fa[i]);
return ans;
}
int dfs(int p,int lp){
int d=0; mxson[p]=0; son[p]=0;
for (auto i:g[p]){
if (i.x!=lp){
d=max(d,dfs(i.x,p)+i.y);
mxson[p]=max(mxson[p],son[i.x]);
son[p]+=son[i.x];
}
}
return d;
}
int hubDistance(int N, int sub) {
vector<int>all;
cnt=N;
d.init(MAXN);
for (int i=0;i<N;i++){
all.push_back(i);
for (int j=i+1;j<N;j++){
dis[i][j]=getDistance(i,j);
dis[j][i]=dis[i][j];
}
}
while (!all.empty())
all=solve(all);
/*
for (int i=0;i<cnt;i++){
cout<<i<<" -> ";
for (auto j:g[i])
cout<<"{"<<j.x<<','<<j.y<<"} ";
cout<<'\n';
}
*/
int mn=1e9,have=-1,p;
for (int i=N;i<cnt;i++){
for (int i=0;i<N;i++)
son[i]=1;
int d=dfs(i,0);
if (d<mn){
mn=min(mn,d);
p=i;
}
}
// cout<<p<<" "<<mn<<'\n';
if (max(mxson[p],N-son[p])<=N/2)
have=1;
return have*mn;
}