Submission #1216590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216590		dreamoon	Race (IOI11_race)	C++20	100 / 100	173 ms	43448 KiB

race

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>
#define SZ(X) (int)(X).size()
using namespace std;
using LL = long long;
const int INF = 1e9;
const int SIZE = 200'001;
vector<pair<int, int>> e[SIZE];
int parent[SIZE];
int ll[SIZE], rr[SIZE], node_id;
LL depth[SIZE];
int edge_num[SIZE];
void dfs(int x, int lt) {
    ll[x] = node_id++;
    int ma = 0, ma_id = -1;
    for (auto &[y, v] : e[x]) {
        if (y == lt) continue;
        depth[node_id] = depth[ll[x]] + v;
        edge_num[node_id] = edge_num[ll[x]] + 1;
        dfs(y, x);
        if (ma < rr[y] - ll[y]) {
            ma = rr[y] - ll[y];
            ma_id = y;
        }
    }
    if (ma_id != -1) parent[ma_id] = x;
    rr[x] = node_id;
}
int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; i++) {
        e[H[i][0]].push_back({H[i][1], L[i]});
        e[H[i][1]].push_back({H[i][0], L[i]});
    }
    fill(parent, parent + N, -1);
    dfs(0, 0);
    int an = INF;
    for (int i = 0; i < N; i++) {
        if (ll[i] + 1 < rr[i]) continue;
        int x = i;
        unordered_map<LL, int> mi;
        auto test = [&](int id, int lca_id) {
            LL need = K + 2 * depth[lca_id] - depth[id];
            if (mi.count(need)) {
                an = min(an, edge_num[id] + mi[need] - 2 * edge_num[lca_id]);
            }
        };
        auto add = [&](int id) {
            LL h = depth[id];
            if (!mi.count(h)) {
                mi[h] = edge_num[id];
            } else {
                mi[h] = min(mi[h], edge_num[id]);
            }
        };
        add(ll[x]);
        while (parent[x] != -1) {
            int p = parent[x];
            for (auto [y, _] : e[p]) {
                if (edge_num[ll[y]] < edge_num[ll[p]] || y == x) continue;
                for (int j = ll[y]; j < rr[y]; j++) test(j, ll[p]);
                for (int j = ll[y]; j < rr[y]; j++) add(j);
            }
            test(ll[p], ll[p]);
            add(ll[p]);
            x = p;
        }
    }
    if (an == INF) an = -1;
    return an;
}

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