Submission #1312243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312243		kawhiet	Race (IOI11_race)	C++20	100 / 100	689 ms	38276 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;

constexpr int N = 2e5 + 5;
constexpr int inf = 1e9;

vector<pair<int, int>> g[N];
int sz[N];
bool deleted[N];

map<int, int> mn;

int k, ans = inf, mx = 0;

void dfs_size(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : g[u]) {
        if (v == p || deleted[v]) continue;
        dfs_size(v, u);
        sz[u] += sz[v];
    }
}

int find_centroid(int u, int p, int n) {
    for (auto [v, w] : g[u]) {
        if (v == p || deleted[v]) continue;
        if (sz[v] * 2 > n) {
            return find_centroid(v, u, n);
        }
    }
    return u;
}

void dfs(int u, int p, int d, int sum, bool upd) {
    if (sum > k) return;
    mx = max(mx, sum);
    if (upd) {
        if (mn.count(sum)) {
            mn[sum] = min(mn[sum], d);
        } else {
            mn[sum] = d;
        }
    } else {
        if (mn.count(k - sum)) {
            ans = min(ans, d + mn[k - sum]);
        }
    }
    for (auto [v, w] : g[u]) {
        if (v == p || deleted[v]) continue;
        dfs(v, u, d + 1, sum + w, upd);
    }
}

void go(int u) {
    dfs_size(u, -1);
    int r = find_centroid(u, -1, sz[u]);
    mx = 0;
    mn[0] = 0;
    for (auto [v, w] : g[r]) {
        if (!deleted[v]) {
            dfs(v, r, 1, w, 0);
            dfs(v, r, 1, w, 1);
        }
    }
    mn.clear();
    deleted[r] = 1;
    for (auto [v, w] : g[r]) {
        if (!deleted[v]) {
            go(v);
        }
    }
}

int best_path(int n, int _k, int h[][2], int l[]) {
    k = _k;
    for (int i = 0; i < n - 1; i++) {
        int u = h[i][0], v = h[i][1], w = l[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    go(0);
    return (ans == inf ? -1 : ans);
}

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