Submission #107048

#	Time	Username	Problem	Language	Result	Execution time	Memory
107048		popovicirobert	Towns (IOI15_towns)	C++14	0 / 100	25 ms	480 KiB

towns

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

using namespace std;

const int INF = (int) 1e9 + 5;

map < pair <int, int>, int > mp;

inline int get(int x, int y) {
    if(x > y) {
        swap(x, y);
    }
    if(x == y) {
        return 0;
    }
    if(mp[{x, y}] != 0) {
        return mp[{x, y}];
    }
    return mp[{x, y}] = getDistance(x, y);
}

int hubDistance(int N, int sub) {

    int i;

    int x = 0;
    for(i = 1; i < N; i++) {
        if(get(0, i) > get(0, x)) {
            x = i;
        }
    }

    int y = 0;
    for(i = 1; i < N; i++) {
        if(get(x, i) > get(x, y)) {
            y = i;
        }
    }

    int R = INF;
    for(i = 0; i < N; i++) {
        int cur = (get(x, i) + get(x, y) - get(y, i)) / 2;
        R = min(R, max(cur, get(x, y) - cur));
    }

    return R;

}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:23: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