Submission #1206278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206278		Aviansh	Towns (IOI15_towns)	C++20	0 / 100	1095 ms	488 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;
    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));
            }
        }
    }
    bool wor = 0;
    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});
                }
                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