Submission #369152

#	Time	Username	Problem	Language	Result	Execution time	Memory
369152		KoD	Towns (IOI15_towns)	C++17	100 / 100	25 ms	492 KiB

towns

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

template <class T>
using Vec = std::vector<T>;

int memo[110][110];
int getDist(const int i, const int j) {
    if (i == j) return 0;
    if (memo[i][j] == 0) {
        memo[i][j] = memo[j][i] = getDistance(i, j);
    }
    return memo[i][j];
}

template <class Comp>
bool majority(const Vec<int> &vec, const Comp &comp) {
    Vec<int> list, bucket;
    for (const auto x: vec) {
        if (list.empty() || !comp(list.back(), x)) {
            list.push_back(x);
            if (!bucket.empty()) {
                list.push_back(bucket.back());
                bucket.pop_back();
            }
        }
        else {
            bucket.push_back(x);
        }
    }
    const auto T = list.back();
    while (!list.empty()) {
        if (comp(list.back(), T)) {
            if (list.size() == 1) {
                bucket.push_back(list.back());
                list.pop_back();
            }
            else {
                list.pop_back();
                list.pop_back();
            }
        }
        else {
            if (bucket.empty()) {
                return false;
            }
            list.pop_back();
            bucket.pop_back();
        }
    }
    return !bucket.empty();
}

int hubDistance(int N, int sub) {
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            memo[i][j] = 0;
        }
    }
    const auto farthest = [&](const int src) {
        Vec<int> v(N);
        std::iota(v.begin(), v.end(), 0);
        return *std::max_element(v.begin(), v.end(), [&](const int i, const int j) {
            return getDist(src, i) < getDist(src, j);
        });
    };
    const auto X = farthest(0);
    const auto Y = farthest(X);
    int R = 1000005;
    std::map<int, Vec<int>> map;
    Vec<int> near(N);
    const auto Diameter = getDist(X, Y);
    for (int u = 0; u < N; ++u) {
        const auto x = getDist(X, u);
        const auto z = ((x + getDist(0, u)) - getDist(X, 0)) / 2;
        const auto l = x - z;
        map[l].push_back(u);
        R = std::min(R, std::max(l, Diameter - l));
        near[u] = z;
    }
    Vec<Vec<int>> cand;
    {
        int left = 0;
        for (const auto &[l, v]: map) {
            if (std::max(left, N - (int) v.size() - left) * 2 <= N && std::max(l, Diameter - l) == R) {
                cand.push_back(v);
            }
            left += (int) v.size(); 
        }
    }
    if (cand.empty()) {
        return -R;
    }
    for (const auto &v: cand) {
        if ((int) v.size() * 2 <= N) {
            return R;
        }
    }
    Vec<char> is_cand(N);
    for (const auto x: cand[0]) {
        is_cand[x] = true;
    }
    const auto same = [&](const int x, const int y) {
        if (!is_cand[x] || !is_cand[y]) return false;
        return getDist(x, y) < near[x] + near[y];
    };
    Vec<int> tmp(N);
    std::iota(tmp.begin(), tmp.end(), 0);
    return majority(tmp, same) ? -R : R;
}

#ifdef LOCAL

int dist[110][110];

int getDistance(int i, int j) {
    return dist[i][j];
}

int main() {
    int sub, tests;
    std::cin >> sub >> tests;
    while (tests--) {
        int N;
        std::cin >> N;
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                std::cin >> dist[i][j];
            }
        }
        std::cout << hubDistance(N, sub) << '\n';
    }
    return 0;
}

#endif

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:54:28: warning: unused parameter 'sub' [-Wunused-parameter]
   54 | int hubDistance(int N, int sub) {
      |                        ~~~~^~~

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