Submission #670273

#	Time	Username	Problem	Language	Result	Execution time	Memory
670273		victor_gao	Towns (IOI15_towns)	C++17	0 / 100	240 ms	524288 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#define MAXN 550
#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];
vector<int>all[MAXN+5];
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();
    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());
        assert(all[i].size()>0);
        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++){
        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 nd=0; mxson[p]=0; son[p]=0;
    for (auto i:g[p]){
        if (i.x!=lp){
            nd=max(nd,dfs(i.x,p)+i.y);
            mxson[p]=max(mxson[p],son[i.x]);
            son[p]+=son[i.x];
        }
    }
    return nd;
}
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];
        }
    }
    int run=0;
    while (!all.empty()){
        run++; assert(run<=100);
        all=solve(all);
    }
    assert(cnt<=500);
    /*
    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 j=0;j<cnt;j++)
            son[j]=0;
        for (int j=0;j<N;j++)
            son[j]=1;
        int nd=dfs(i,-1);
        if (nd<mn){
            mn=min(mn,nd);
            p=i;
        }
    }
   // cout<<p<<" "<<mn<<'\n';
    if (max(mxson[p],N-son[p])<=N/2)
        have=1;
    return have*mn;
}

Compilation message (stderr)

towns.cpp: In function 'std::vector<int> solve(std::vector<int>)':
towns.cpp:26:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   26 |     int n=have.size();
      |           ~~~~~~~~~^~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:91:16: warning: declaration of 'all' shadows a global declaration [-Wshadow]
   91 |     vector<int>all;
      |                ^~~
towns.cpp:10:12: note: shadowed declaration is here
   10 | vector<int>all[MAXN+5];
      |            ^~~
towns.cpp:90:28: warning: unused parameter 'sub' [-Wunused-parameter]
   90 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 39