Submission #727427

#	Time	Username	Problem	Language	Result	Execution time	Memory
727427		vjudge1	Towns (IOI15_towns)	C++11	25 / 100	16 ms	1072 KiB

towns

#include "towns.h"

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

const int MAXN = 110;
int f[2][MAXN];

int hubDistance(int N, int sub) {
        int a = 0, b = -1, best = -1;
        for (int i = 1; i < N; i++) {
                int ans = getDistance(a, i);
                if (ans > best) best = ans, b = i;
        }
        f[1][a] = best;
        for (int i = 1; i < N; i++) {
                int ans = getDistance(i, b);
                if (ans > best) best = ans, a = i;
                f[1][i] = ans;
        }
        for (int i = 0; i < N; i++) {
                f[0][i] = getDistance(a, i);
        }
        int res = 1e9;
        for (int i = 0; i < N; i++) {
                res = min(res, max({f[0][i] + f[1][i] - best, f[0][i] + best - f[1][i], f[1][i] + best - f[0][i]}));
        }
        return res / 2;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:9:28: warning: unused parameter 'sub' [-Wunused-parameter]
    9 | 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