Submission #234952

#	Time	Username	Problem	Language	Result	Execution time	Memory
234952		dolphingarlic	Towns (IOI15_towns)	C++14	0 / 100	24 ms	400 KiB

towns

#include "towns.h"

inline int max(int X, int Y) { return (X > Y ? X : Y); }

int to_0[110], A, to_A[110], B;
int R = 1000001, hubs[2], hub_cnt = 0;

int hubDistance(int N, int sub) {
    for (int i = 1, best_A = 0; i < N; i++) {
        to_0[i] = getDistance(0, i);
        if (to_0[i] > best_A) A = i, best_A = to_0[i];
    }
    to_A[0] = to_0[A];
    for (int i = 0, best_B = 0; i < N; i++) {
        if (i == A) continue;
        to_A[i] = getDistance(A, i);
        if (to_A[i] > best_B) B = i, best_B = to_A[i];
    }

    for (int i = 0; i < N; i++) {
        int A_to_potential_hub = (to_A[i] + to_A[0] - to_0[i]) / 2;
        int potential_R = max(A_to_potential_hub, to_A[B] - A_to_potential_hub);

        if (potential_R < R) R = potential_R, hub_cnt = 0;
        if (potential_R == R) hubs[hub_cnt++] = i;
    }

    return R;
}

Compilation message (stderr)

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

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