Submission #529277

#	Time	Username	Problem	Language	Result	Execution time	Memory
529277		Cyanmond	Towns (IOI15_towns)	C++17	25 / 100	19 ms	948 KiB

towns

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

template <typename T> bool setmax(T &v, const T a) {
    if (v < a) {
        v = a;
        return true;
    } else {
        return false;
    }
}

template <typename T> bool setmin(T &v, const T a) {
    if (v > a) {
        v = a;
        return true;
    } else {
        return false;
    }
}

constexpr int max_d = 1000010;

int hubDistance(int N, int sub) {
    if (sub == 1 or sub == 2) {
        std::vector<int> dist;
        auto find_maxdist = [&](const int v, std::vector<int> &d) {
            int max = 0, pos = 0;
            for (int i = 0; i < N; ++i) {
                d[i] = getDistance(v, i);
                if (setmax(max, d[i])) {
                    pos = i;
                }
            }
            return std::make_pair(pos, max);
        };

        std::vector<int> memo(N);
        const auto [p1, v1] = find_maxdist(0, memo);
        const auto [p2, diameter] = find_maxdist(p1, memo);

        int res = max_d;
        for (int i = 0; i < N; ++i) {
            if (i == p1 or i == p2) continue;
            const int d1 = memo[i], d2 = getDistance(p2, i);
            const int r = ((d1 + d2) - diameter) / 2;
            setmin(res, std::max(d1 - r, d2 - r));
        }

        return res;
    } else {
        return 0;
    }
}

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