Submission #1211365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211365		mountainsalt	Race (IOI11_race)	C++20	100 / 100	512 ms	40332 KiB

race

#include <bits/stdc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int, int>

using namespace std;

const int N = 2e5 + 5;
const int K = 1e6 + 5;
const int inf = 1e18;

int n, k, ans = inf, sz[N], cal[K];
vector <pii> adj[N], temp;
bool del[N];

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

int centroid(int u, int p, int siz){
    for (auto [w, v] : adj[u]) {
        if (v == p || del[v]) continue;
        if (2 * sz[v] > siz) return centroid(v, u, siz);
    }
    return u;
}

void dfs(int u, int p, int dis, int cnt){
    temp.emb(dis, cnt);
    if (k >= dis && cal[k - dis] != inf) ans = min(ans, cnt + cal[k - dis]);
    for (auto [w, v] : adj[u]) {
        if (v == p || del[v]) continue;
        dfs(v, u, dis + w, cnt + 1);
    }
}

void dfsdel(int u, int p, int dis){
    if (dis <= k) cal[dis] = inf;
    for (auto [w, v] : adj[u]) {
        if (v == p || del[v]) continue;
        dfsdel(v, u, dis + w);
    }
}

void decompose(int u){
    dfssz(u, u);
    u = centroid(u, u, sz[u]);
    del[u] = true;
    cal[0] = 0;
    for (auto [w, v] : adj[u]) {
        if (del[v]) continue;
        temp.clear();
        dfs(v, u, w, 1);
        for (auto [dis, cnt] : temp) {
            if (dis <= k) cal[dis] = min(cal[dis], cnt);
        }
    }
    for (auto [w, v] : adj[u]) {
        if (del[v]) continue;
        dfsdel(v, u, w);
    }
    for (auto [w, v] : adj[u]) {
        if (!del[v]) decompose(v);
    }
}

int32_t best_path(int32_t nn, int32_t kk, int32_t edge[][2], int32_t wei[]){
    n = nn, k = kk;
    for (int i = 0; i <= k; i++) cal[i] = inf;
    for (int i = 0; i < n - 1; i++) {
        auto v = edge[i];
        adj[v[0]].emb(wei[i], v[1]);
        adj[v[1]].emb(wei[i], v[0]);
    }
    decompose(0);
    return (ans == inf ? -1 : ans);
}

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