Submission #1163008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163008		tosivanmak	Towns (IOI15_towns)	C++20	13 / 100	10 ms	616 KiB

towns

#include<bits/stdc++.h>
#include "towns.h"
using namespace std;
#define ll long long

struct DSU{
    vector<ll>fa,siz;

    void init(ll n){
        fa.resize(n+5); siz.resize(n+5);
        for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
    }
    ll root(ll x){
        if(fa[x]==x)return x;
        return fa[x]=root(fa[x]);
    }
    void unite(ll u, ll v){
        u=root(u); v=root(v);
        if(u==v)return;
        if(siz[u]<siz[v])swap(u,v);
        siz[u]+=siz[v]; fa[v]=u;
    }
};
bool asked[150][150];
ll dist[150][150];

int get(int i, int j){
    if(i==j){
        dist[i][j]=0; asked[i][j]=1;
        return dist[i][j];
    }
    if(asked[i][j]){
        return dist[i][j];
    }
    dist[i][j]=dist[j][i]=getDistance(i,j);
    asked[i][j]=asked[j][i]=1;
    return dist[i][j];
}
int hubDistance(int N, int sub){
    // getDistance(i, j)
    for(int i=0;i<150;i++){
        for(int j=0;j<150;j++){
            asked[i][j]=0;
        }
    }
    ll initial[150];
    for(int i=0;i<N;i++){
        initial[i]=get(0,i);
    }
    ll fur=-1,nd=-1;
    for(int i=0;i<N;i++){
        if(initial[i]>fur){
            fur=initial[i]; nd=i;
        }
    }
    ll dia[150];
    for(int i=0;i<N;i++){
        dia[i]=get(nd,i);
    }
    ll fur2=-1,nd2=-1;
    for(int i=0;i<N;i++){
        if(dia[i]>fur2){
            fur2=dia[i]; nd2=i;
        }
    }
    // nd,nd2 forms the diameter
    // how far away from nd
    ll dep[155];
    dep[nd]=0; dep[nd2]=0;
    ll diameter=get(nd,nd2);
    dep[0]=get(0,nd)+get(0,nd2)-diameter;
    dep[0]/=2;
    ll fromnd=get(0,nd)-dep[0];
    ll fromnd2=get(0,nd2)-dep[0];
    for(int i=1;i<N;i++){
        ll diff=get(0,i)+get(i,nd)-get(0,nd);
        ll req=(diff+2*fromnd);
        if(req==2*get(nd,i)){
            // closer to nd2
            dep[i]=(get(nd2,i)+get(nd,i)-diameter)/2;
        }
        else{
            ll tryy=diff/2;
            ll chn=get(i,nd)-tryy;
            if(chn>fromnd){
                chn=get(0,nd)-dep[0];
                dep[i]=get(i,nd)-chn;
            }
            else{
                dep[i]=tryy;
            }
        }
        // dep[i]=(get(nd2,i)+get(nd,i)-diameter)/2;
    }
    vector<ll>dists;
    for(int i=0;i<N;i++){
        dists.push_back(get(nd,i)-dep[i]);
    }
    sort(dists.begin(),dists.end());
    dists.erase(unique(dists.begin(),dists.end()),dists.end());
    ll ans=1e18; vector<ll>cand;
    for(int i=0;i<dists.size();i++){
        ll val=max(dists[i],diameter-dists[i]);
        if(val<ans){
            cand.clear();
            ans=val;
            cand.push_back(dists[i]);
        }
        else if(val==ans){
            cand.push_back(dists[i]);
        }
    }
    bool ok=0;
    for(auto& u: cand){
        ll cnt=0;
        for(int i=0;i<N;i++){
            if(dists[i]==u){
                cnt++;
            }
        }
        ll smol=0,lar=0;
        if(cnt<=N/2){
            // no checking 
            for(int i=0;i<N;i++){
                if(dists[i]<u)smol++;
                else if(dists[i]>u)lar++;
            }
            if(smol<=N/2&&lar<=N/2)ok=1;
        }
        else{
            // since cnt > N/2 others <= N/2
            vector<ll>req;
            req.push_back(0);
            for(int i=0;i<N;i++){
                if(dists[i]==u)req.push_back(i);
            }
            DSU d;
            d.init(req.size());
            bool used[req.size()+5];
            for(int i=0;i<req.size()+5;i++)used[i]=0;
            ll ptrl=1,ptrr=1;
            while(ptrr<req.size()){
                if(ptrl==ptrr){ptrr++; continue;}
                if(used[ptrr]){ptrr++; continue;}
                if(used[ptrl]){ptrl++; continue;}
                ll dt=get(req[ptrl],req[ptrr]);
                ll real=dep[req[ptrl]]+dep[req[ptrr]];
                if(real==dt){
                    used[ptrl]=used[ptrr]=1; ptrl++; ptrr++;
                }
                else{
                    d.unite(ptrl,ptrr); ptrr++;
                }
            }
            ll id=-1;
            for(int i=1;i<req.size();i++){
                if(!used[i]){
                    id=i; break;
                }
            }
            if(id==-1){
                return ans;
            }
            for(int i=1;i<req.size();i++){
                if(d.root(i)!=d.root(id)&&d.root(i)==i){
                    ll dt=get(req[i],req[id]);
                    ll real=dep[req[id]]+dep[req[i]];
                    if(dt!=real){
                        d.unite(i,id);
                    }
                }
            }
            if(d.siz[d.root(id)]<=N/2)ok=1;
        }
    }
    if(ok)return ans;
    else return -ans;
}

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