Submission #795393

#	Time	Username	Problem	Language	Result	Execution time	Memory
795393		jasmin	Towns (IOI15_towns)	C++17	25 / 100	16 ms	884 KiB

towns

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

int hubDistance(int n, int sub) {

    //find diameter
    vector<int> dist0(n);
    int a=1;
    for(int i=1; i<n; i++){
        dist0[i] = getDistance(0, i);

        if(dist0[i]>dist0[a]){
            a=i;
        }
    }

    int b=0;
    vector<int> dista(n);
    dista[0] = dist0[a];
    for(int i=1; i<n; i++){
        if(i==a) continue;

        dista[i] = getDistance(a, i);

        if(dista[i] > dista[b]){
            b=i;
        }
    }

    vector<int> distb(n);
    distb[0] = dist0[b];
    distb[a] = dista[b];
    for(int i=1; i<n; i++){
        if(i==a || i==b) continue;

        distb[i] = getDistance(b, i);
    }

    int diameter = dista[b];



    //group the leafes
    vector<int> dleft(n); dleft[a]=0; dleft[b]=diameter;
    vector<int> ddiam(n); ddiam[a]=ddiam[b]=0;

    map<int, vector<int> > group;
    for(int i=0; i<n; i++){
        if(i==a || i==b) continue;

        ddiam[i] = (dista[i]+distb[i] - diameter)/2;
        dleft[i] = dista[i]-ddiam[i];

        group[dleft[i]].push_back(i);
    }



    //compute r
    
    int r=diameter;
    for(auto [x, g]: group){

        r = min(r, max(x, diameter-x));
    }
    return r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:5:28: warning: unused parameter 'sub' [-Wunused-parameter]
    5 | int hubDistance(int n, int sub) {
      |                        ~~~~^~~

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