Submission #1206282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206282		Aviansh	Towns (IOI15_towns)	C++20	0 / 100	1096 ms	4536 KiB

towns

#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 hubDistance(int n, int sub) {
	//int R = getDistance(0,1);
	int dist[n][n];
	for(int i = 0;i<n;i++){
        fill(dist[i],dist[i]+n,0);
	}
	for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            dist[i][j]=dist[j][i]=getDistance(i,j);
        }
	}
	int ans = 2e9;
	set<array<int,3>>mxs;
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++){
            for(int k = j+1;k<n;k++){
                int dists[n];
                int a = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[j][k];
                int b = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][k];
                int c = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][j];
                for(int l = 0;l<n;l++){
                    dists[l]=max({dist[i][l]-a,dist[j][l]-b,dist[k][l]-c});
                }
                ans=min(ans,*max_element(dists,dists+n));
                if(ans==*max_element(dists,dists+n)){
                    mxs.insert({i,j,k});
                }
            }
        }
    }
    bool wor = 0;
    for(array<int,3>aa : mxs){
        int i,j,k;
        i=aa[0];
        j=aa[1];
        k=aa[2];
        int dists[n];
        int a = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[j][k];
        int b = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][k];
        int c = ((dist[i][j]+dist[j][k]+dist[i][k])/2)-dist[i][j];
        for(int l = 0;l<n;l++){
            dists[l]=max({dist[i][l]-a,dist[j][l]-b,dist[k][l]-c});
        }
        if(ans==*max_element(dists,dists+n)){
            //valid.
            //count out now
            dsu ds(n);
            for(int i = 0;i<n;i++){
                for(int j = i+1;j<n;j++){
                    if(dists[i]+dists[j]>dist[i][j]){
                        ds.unite(i,j);
                    }
                }
            }
            if(ds.mxsiz<=n/2){
                wor=1;
            }
        }
    }
    if(!wor)
        ans=-ans;
	return ans;
}

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