Submission #1243414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243414		ASGA_RedSea	Towns (IOI15_towns)	C++20	38 / 100	10 ms	328 KiB

towns

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA"


#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>


using namespace std;
using ll=long long;

int getDistance(int i,int j);

#include"towns.h"



vector<vector<int>>d;
int g(int i,int j){
    if(i>j)swap(i,j);
    return (i!=j&&d[i][j]==0?(d[i][j]=getDistance(i,j)):d[i][j]);
}



vector<int>F,sz;
int find(int i){
    return (F[i]==i?i:(F[i]=find(F[i])));
}
void uni(int x,int y){
    x=find(x);y=find(y);
    if(x!=y){
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        F[y]=x;
    }
}

int hubDistance(int n,int sbt){
    d.assign(n,vector<int>(n,0));


    int a=0,b=0,mmx=0;
    for(int i=0;i<n;i++){
        if(g(i,a)>mmx){
            mmx=g(i,a);
            b=i;
        }
    }

    set<vector<array<int,2>>>c;
    int ans=1e6,f=0;
    {
        set<int>s;
        for(int i=0;i<n;i++){
            if(i==a||i==b)continue;
            s.insert((g(a,i)+g(a,b)-g(i,b))/2);
        }
        for(auto&ds:s){
            int mx=max(ds,g(a,b)-ds);
            for(int k=0;k<n;k++){
                if(k==a||k==b)continue;
                int dd=(g(a,b)+g(a,k)-g(b,k))/2;
                mx=max(mx,(g(a,k)+g(b,k)-g(a,b))/2+abs(dd-ds));
            }
            ans=min(ans,mx);
        }

        if(sbt<3)return ans;

        for(auto&ds:s){
            vector<array<int,2>>dds;
            int mx=max(ds,g(a,b)-ds);
            int sz[3]{};
            for(int k=0;k<n;k++){
                if(k==a||k==b){
                    dds.push_back(k==a?array<int,2>{ds,a}:array<int,2>{d[a][b]-ds,b});
                    continue;
                }
                int dd=(g(a,b)+g(a,k)-g(b,k))/2;
                mx=max(mx,(g(a,k)+g(b,k)-g(a,b))/2+abs(dd-ds));
                dds.push_back({(g(a,k)+g(b,k)-g(a,b))/2+abs(dd-ds),k});
                sz[(ds<dd?0:(ds==dd?1:2))]++;
            }
            if(ans==mx){
                if(sbt==4&&(max({sz[0],sz[1],sz[2]})<=n/2))return ans;
                if(sbt>2&&sbt!=4)c.insert(dds);
            }
        }
    }

    if(sbt==4)return -ans;

    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)d[j][i]=g(i,j);


    f=0;
    for(auto&s:c){
        vector<int>dis(n);
        for(auto&[i,j]:s)dis[j]=i;

        F.resize(n);
        iota(F.begin(),F.end(),0);
        sz.assign(n,1);
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(g(i,j)<dis[i]+dis[j]){
                    uni(i,j);
                }
            }
        }
        int mx=0;
        for(int i=0;i<n;i++)mx=max(mx,sz[find(i)]);

        if(mx<=n/2)return ans;
    }

    return -ans;
}

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