Submission #699982

#	Time	Username	Problem	Language	Result	Execution time	Memory
699982		elkernos	Race (IOI11_race)	C++17	0 / 100	1 ms	340 KiB

race

#include "race.h"
#include "bits/stdc++.h"

using namespace std;

#define ssize(x) (int)size(x)
template <class A, class B>
auto &operator<<(ostream &o, pair<A, B> p)
{
    return o << '(' << p.first << ", " << p.second << ')';
}
template <class T>
auto operator<<(ostream &o, T x) -> decltype(x.end(), o)
{
    o << '{';
    int i = 0;
    for (auto e : x)
        o << (", ") + 2 * !i++ << e;
    return o << '}';
}
#ifdef DEBUG
#define debug(x...) cerr << "[" #x "]: ", [](auto... $) { ((cerr << $ << "; "), ...); }(x), cerr << '\n'
#else
#define debug(...) \
    {              \
    }
#endif

int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pair<int, int>>> graf(N);
    for (int i = 0; i < N; i++) {
        int a = H[i][0], b = H[i][1], c = L[i];
        graf[a].push_back({b, c});
        graf[b].push_back({a, c});
    }
    const int oo = 1e9 + 2133;
    int ans = oo;
    vector<int> subsz(N);
    vector<bool> used(N);
    function<void(int, int)> calc_sz = [&](int u, int p) {
        subsz[u] = 1;
        for (auto [to, _] : graf[u]) {
            if (to == p || used[to]) continue;
            calc_sz(to, u);
            subsz[u] += subsz[to];
        }
    };
    function<int(int, int, int)> calc_centro = [&](int u, int p, int need) {
        for (auto [to, _] : graf[u]) {
            if (to == p || used[to]) continue;
            if (subsz[to] * 2 > need) return calc_centro(to, u, need);
        }
        return u;
    };
    vector<vector<pair<int, int>>> wek(K + 1);
    vector<int> cos;
    int pid = 0;
    function<void(int, int, int, int, int)> gather = [&](int u, int p, int len, int path_id, int edges_count) {
        if (len <= K) {
            wek[len].push_back({edges_count, path_id});
            cos.push_back(len);
        }
        else return; // xD?
        for (auto [to, tlen] : graf[u]) {
            if (to == p || used[to]) continue;
            gather(to, u, len + tlen, path_id, edges_count + 1);
        }
    };
    function<void(int)> rek = [&](int u) {
        calc_sz(u, u);
        u = calc_centro(u, u, subsz[u]);
        for (auto [to, tlen] : graf[u]) {
            if (used[to]) continue;
            gather(to, u, tlen, ++pid, 1);
        }
        cos.push_back(0);
        wek[0].push_back({0, -1});
        sort(cos.begin(), cos.end());
        cos.erase(unique(cos.begin(), cos.end()), cos.end());
        for (auto x : cos) {
            pair<int, int> min_1(N, 0), min_2(N, 0);
            for (auto d : wek[x]) {
                if (min_1 > d) {
                    min_2 = min_1;
                    min_1 = d;
                }
                else if (min_2 > d) min_2 = d;
            }
            for (auto d : wek[K - x]) {
                if (d.second != min_1.second) ans = min(ans, d.first + min_1.first);
                if (d.second != min_2.second) ans = min(ans, d.first + min_2.first);
            }
        }
        used[u] = 1;
        for (auto x : cos) {
            wek[x].clear();
        }
        cos.clear();
        for (auto [to, _] : graf[u]) {
            if (used[to]) continue;
            rek(to);
        }
    };
    rek(1);
    return (ans >= N ? -1 : ans);
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57