Submission #494860

#	Time	Username	Problem	Language	Result	Execution time	Memory
494860		thecodingwizard	Towns (IOI15_towns)	C++11	25 / 100	16 ms	1068 KiB

towns

#include <bits/stdc++.h>
#include "towns.h"

using namespace std;

#define ii pair<int, int>
#define mp make_pair
#define inf 1e9;

map<ii, int> cached;
int getD(int a, int b) {
    if (a == b) return 0;
    if (a > b) swap(a, b);
    if (cached.count(mp(a, b))) return cached[mp(a, b)];
    return cached[mp(a, b)] = getDistance(a, b);
}

int hubDistance(int N, int sub) {
    cached.clear();

    int u, v;

    int maxDist = -1;
    for (int i = 0; i < N; i++) {
        if (getD(0, i) > maxDist) {
            maxDist = getD(0, i);
            u = i;
        }
    }

    maxDist = -1;
    for (int i = 0; i < N; i++) {
        if (getD(u, i) > maxDist) {
            maxDist = getD(u, i);
            v = i;
        }
    }

    int opt = inf;
    for (int i = 0; i < N; i++) {
        int distFromHubToU = (getD(u, i) + getD(u, 0) - getD(i, 0))/2;
        int distFromHubToV = getD(u, v) - distFromHubToU;
        opt = min(opt, max(distFromHubToU, distFromHubToV));
    }

    return opt;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:18:28: warning: unused parameter 'sub' [-Wunused-parameter]
   18 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~
towns.cpp:42:34: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   42 |         int distFromHubToV = getD(u, v) - distFromHubToU;
      |                              ~~~~^~~~~~
towns.cpp:42:34: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]

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