Submission #1196690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196690		quannnguyen2009	Race (IOI11_race)	C++20	31 / 100	325 ms	38112 KiB

race

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

const int N=2e5+5, mod = 1e9+7, inf = 1e18;
 
struct Edge {
    int to, w;
};
 
int n, k;
vector<Edge> adj[N];
bool del[N];
int sz[N], dist[10*N];
int ans = inf;
 
void dfs(int v, int 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(int v, int p=-1, int sum=0, int 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(int v, int p=-1, int sum=0, int 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(int v, int p = -1, int 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);
    }
}
 
int centroid(int v, int p, int 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(int 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 (int i=0; i<n-1; i++) {
        int 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 (int i=0; i<=10*n-1; i++) dist[i] = inf;
    dfs(0);
    solve(centroid(0, -1, sz[0]));
    if (ans==inf) return -1;
    return ans;
}

Compilation message (stderr)

race.cpp:11:39: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const int N=2e5+5, mod = 1e9+7, inf = 1e18;
      |                                       ^~~~

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