제출 #586663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
586663		InternetPerson10	도시들 (IOI15_towns)	C++17	0 / 100	18 ms	1120 KiB

towns

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

using namespace std;

map<pair<int, int>, int> distances;

int getDist(int i, int j) {
    if(i == j) return 0;
    if(i > j) swap(i, j);
    if(distances.count({i, j})) {
        return distances[make_pair(i, j)];
    }
    return distances[make_pair(i, j)] = getDistance(i, j);
}

vector<int> dists;

int hubDistance(int N, int sub) {
    int ans = 2e9 + 7;
    dists.resize(N);
    int ma = -1, best = -1;
    for(int i = 0; i < N; i++) {
        dists[i] = getDist(0, i);
        if(ma < dists[i]) {
            ma = dists[i];
            best = i;
        }
    }
    int x = best;
    ma = -1, best = -1;
    for(int i = 0; i < N; i++) {
        dists[i] = getDist(x, i);
        if(ma < dists[i]) {
            ma = dists[i];
            best = i;
        }
    }
    int y = best;
    int c = ma;
    for(int i = 0; i < N; i++) {
        if(i == x || i == y) continue;
        int a = getDist(x, i);
        int b = getDist(y, i);
        ans = min(ans, max((a + c - b) / 2, (b + c - a) / 2));
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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