Submission #953627

#	Time	Username	Problem	Language	Result	Execution time	Memory
953627		nickshen	Race (IOI11_race)	C++17	0 / 100	1 ms	2648 KiB

race

#include <bits/stdc++.h>
using namespace std;
vector<int> sum, dist;
vector<vector<pair<int,int>>> v;
vector<map<int, int>> vm;
void pre(int n, int p, int s, int d) {
    vm[n][s] = d;
    sum[n] = s;
    dist[n] = d;
    for (auto [i, j] : v[n]) {
        if (i != p) {
            pre(i, n, s + j, d + 1);
        }
    }
}
int tar, ans;
void dfs(int n, int p) {
    int cur = tar + 2 * sum[n];
    for (auto [i, j] : v[n]) {
        if (i != p) {
            dfs(i, n);
            // small-to-large
            if (vm[i].size() > vm[n].size()) {
                swap(vm[i], vm[n]);
            }
            for (auto [t, b] : vm[i]) {
                if (vm[n].find(cur - t) != vm[n].end()) {
                    ans = min(ans, vm[n][cur - t] + b - 2 * dist[n]);
                }
            }
            for (auto [t, b] : vm[i]) {
                if (vm[n].find(t) == vm[n].end())
                    vm[n][t] = b;
                else
                    vm[n][t] = min(vm[n][t], b);
            }
        }
    }
}

int best_path(int n, int k, int edges[][2], int weights[]) {
    if (k == 1) { return 0; }
    v.resize(n);
    sum.resize(n);
    dist.resize(n);
    tar = k;
    vm.resize(n);
    ans = 1e9;
    for (int i = 0; i < n; i++) {
        int a = edges[i][0], b = edges[i][1], w = weights[i];
        v[a].push_back({b, w});
        v[b].push_back({a, w});
    }
    pre(0, -1, 0, 0);
    dfs(0, -1);
    return (ans == 1e9 ? -1 : ans);
}

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