Submission #922007

#	Time	Username	Problem	Language	Result	Execution time	Memory
922007		Beerus13	Race (IOI11_race)	C++17	100 / 100	259 ms	40900 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pii pair<int, int>
const int N = 2e5 + 5;
const int K = 1e6 + 5;
const int inf = 1e9;

int n, k;
int dp[K], val[N], dep[N], cnt[N], sz[N];
bool del[N];
vector<pii> g[N];
vector<int> node, tree;
int ans = inf;

int dfs_size(int u, int p = 0) {
    sz[u] = 1;
    for(auto [v, _] : g[u]) if(v != p && !del[v]) sz[u] += dfs_size(v, u);
    return sz[u];
}

int find_centroid(int u, int p, int num) {
    for(auto [v, _] : g[u]) if(v != p && !del[v] && sz[v] > num / 2) return find_centroid(v, u, num);
    return u;
}

void dfs_centroid(int u, int p) {
    if(val[u] > k) return;
    dep[u] = dep[p] + 1;
    node.push_back(u);
    tree.push_back(u);
    ans = min(ans, dep[u] + dp[k - val[u]]);
    for(auto [v, w] : g[u]) if(v != p && !del[v]) {
        val[v] = val[u] + w;
        dfs_centroid(v, u);
    }
}

void decomposition(int u) {
    int centroid = find_centroid(u, 0, dfs_size(u));
    del[centroid] = 1;
    dep[centroid] = val[centroid] = dp[0] = 0;
    tree.push_back(centroid);
    for(auto [v, w] : g[centroid]) if(!del[v]) {
        val[v] = w;
        dfs_centroid(v, centroid);
        for(int x : node) dp[val[x]] = min(dp[val[x]], dep[x]);
        node.clear();
    }
    for(int x : tree) dp[val[x]] = inf;
    tree.clear();
    for(auto [v, _] : g[centroid]) if(!del[v]) {
        decomposition(v);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    for(int i = 0; i < N - 1; ++i) {
        int u = H[i][0], v = H[i][1], w = L[i];
        ++u; ++v;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    memset(dp, 0x3f, sizeof(dp));
    decomposition(1);
    return ans == inf ? -1 : ans;
}

// void solve() {
//     cin >> n >> k;
//     for(int i = 1, u, v, w; i < n; ++i) {
//         cin >> u >> v >> w;
//         ++u; ++v;
//         g[u].emplace_back(v, w);
//         g[v].emplace_back(u, w);
//     }
//     memset(dp, 0x3f, sizeof(dp));
//     decomposition(1);
//     cout << (ans == inf ? -1 : ans) << '\n';
// }
 
// signed main() {
//     ios::sync_with_stdio(0);
//     cin.tie(0); cout.tie(0);
//     int test = 1;
//     // cin >> test;
//     while(test--) solve();
//     return 0;
// }

// https://oj.uz/problem/view/IOI11_race

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