Submission #1196692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196692		quannnguyen2009	Race (IOI11_race)	C++20	31 / 100	334 ms	46744 KiB

race

#include<bits/stdc++.h>
// #define long long long long
#define fi first
#define se second
#define pb push_back
#define ii pair<long long, long long>
#define sz(v) (long long)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const long long N=2e5+5, mod = 1e9+7, inf = 1e18;
 
struct Edge {
    long long to, w;
};
 
long long n, k;
vector<Edge> adj[N];
bool del[N];
long long sz[N], dist[10*N];
long long ans = inf;
 
void dfs(long long v, long long p=-1) {
    sz[v] = 1;
    for (auto [u, w]:adj[v]) {
        if (u!=p && !del[u]) {
            dfs(u, v);
            sz[v]+=sz[u];
        }
    }
}
 
void dfs_ans(long long v, long long p=-1, long long sum=0, long long d=0) {
    if (k<sum) return;
    if (dist[k-sum]<inf) ans = min(ans, dist[k-sum]+d);
    for (auto [u, w]:adj[v]) {
        if (u!=p && !del[u]) dfs_ans(u, v, sum+w, d+1);
    }
}
 
void upd(long long v, long long p=-1, long long sum=0, long long d=0) {
    if (k<sum) return;
    dist[sum] = min(dist[sum], d);
    for (auto [u, w] : adj[v]) {
        if (u!=p && !del[u]) upd(u, v, sum+w, d+1);
    }
}
 
void init(long long v, long long p = -1, long long sum = 0) {
    if (k<sum) return;
    dist[sum] = inf;
    for (auto [u, w] : adj[v]) {
        if (u!=p && !del[u]) init(u, v, sum+w);
    }
}
 
long long centroid(long long v, long long p, long long nn) {
    for (auto [u, w] : adj[v]) {
        if (u!=p && !del[u]) {
            if (sz[u]*2>nn) return centroid(u, v, nn);
        }
    }
    return v;
}
 
void solve(long long v) {
    dfs(v);
    dist[0] = 0;
    for (auto [u, w] : adj[v]) {
        if (!del[u]) {
            dfs_ans(u, v, w, 1);
            upd(u, v, w, 1);
        }
    }
    init(v);
    del[v] = 1;
    for (auto [u, w] : adj[v]) {
        if (!del[u]) solve(centroid(u, v, sz[u]));
    }
}
 
int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    for (long long i=0; i<n-1; i++) {
        long long u, v, w;
        u = H[i][0]; v = H[i][1]; w = L[i];
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    for (long long i=0; i<=10*n-1; i++) dist[i] = inf;
    dfs(0);
    solve(centroid(0, -1, sz[0]));
    if (ans==inf) return -1;
    return (int) ans;
}

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