Submission #1264077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264077		nguyenvietanh	Race (IOI11_race)	C++20	100 / 100	466 ms	36460 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define inp(name) freopen(name, "r", stdin);
#define out(name) freopen(name, "w", stdout);
const int N = 2e5 + 5;
int n, k;
int s[N], vst[N], mn[5 * N], tin[5 * N];
vector <pii> adj[N];
int timer = 0;
void pre_dfs (int u, int v){
    s[u] = 1;
    for (auto [i, w] : adj[u]){
        if (vst[i] || i == v) continue;
        pre_dfs(i, u);
        s[u] += s[i];
    }
}
int centroid (int u, int v, int n){
    for (auto [i, w] : adj[u]){
        if (vst[i] || i == v) continue;
        if (s[i] <= n/2) continue;
        return centroid(i, u, n);
    }
    return u;
}
int ans = INT_MAX;
void add(int u, int v, int len, int dist){
    if (dist <= k && tin[k - dist] == timer){
        ans = min(ans, len + mn[k - dist]);
    }
    for (auto [i, w] : adj[u]){
        if (i == v || vst[i]) continue;
        add(i, u, len + 1, dist + w);
    }
}
void dfs_dist(int u, int v, int len, int dist){
    if (dist <= k){
        if (tin[dist] != timer){
            mn[dist] = len;
            tin[dist] = timer;
        }
        else mn[dist] = min(mn[dist], len);
    }
    for (auto [i, w] : adj[u]){
        if (i == v || vst[i]) continue;
        dfs_dist(i, u, len + 1, dist + w);
    }
}
void dnc(int u){
    pre_dfs(u, 0);
    int c = centroid(u, 0, s[u]);
    tin[0] = ++timer;
    for (auto [i, w] : adj[c]){
        if (vst[i]) continue;
        add(i, c, 1, w);
        dfs_dist(i, c, 1, w);
    }
    vst[c] = 1;
    for (auto [i, w] : adj[c]){
        if (vst[i]) continue;
        dnc(i);
    }
}
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] + 1, v = H[i][1] + 1, w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    fill (mn + 1, mn + k + 5, 1e9);
    dnc(1);
    if (ans > 1e9) ans = -1;
    return ans;
}

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