Submission #1250224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250224		khoavn2008	Race (IOI11_race)	C++20	0 / 100	3 ms	5188 KiB

race

#include "race.h"

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ld double
#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define REP(i,r) for(ll i=0,_r=(r);i<_r;i++)
#define FOR(i,l,r) for(ll i=(l),_r=(r);i<=_r;i++)
#define FORE(i,v) for(__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define FORNG(i,r,l) for(ll i=(r),_l=(l);i>=_l;i--)
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1LL)
#define all(v) (v).begin(),(v).end()
#define size(v) ((ll)(v).size())

const ll MOD = 1e9+7, N = 2e5+10, INF = 1e9, LOG = 20;
ll n,k,ans = INF;
vector<pair<ll,ll>> adj[N];
bool del[N];
ll sz[N],f[(ll)1e6 + 10];
ll get_sz(ll u,ll par = -1){
    sz[u] = 1;
    for(auto [v, w] : adj[u])if(v != par && !del[v])
        sz[u] += get_sz(v, u);
    return sz[u];
}
ll find_centroid(ll u,ll par,ll base){
    for(auto [v, w] : adj[u])if(!del[v] && v != par && sz[v] * 2 >= base){
        return find_centroid(v, u, base);
    }
    return u;   
}
void dfs(ll u,ll par,ll d,ll high,ll state){
    if(state == 0){
        if(d <= k)ans = min(ans, high + f[k - d]);
    }
    if(state == 1){
        if(d <= k)f[d] = min(f[d], high);
    } 
    if(state == 2){
        f[d] = INF;
    }
    for(auto [v, w] : adj[u]){
        if(del[v] || v == par)continue;
        dfs(v, u, d + w, high + 1, state);
    }
}
void centroid_dcp(ll u){
    ll root = find_centroid(u, -1, get_sz(u));
    del[root] = 1;
    f[0] = 0;
    for(auto [v, w] : adj[root])if(!del[v]){
        dfs(v, root, w, 1, 0);
        dfs(v, root, w, 1, 1);
    }
    for(auto [v, w] : adj[root])if(!del[v]){
        dfs(v, root, w, 1, 2);
    }
    for(auto [v, w] : adj[root])if(!del[v])centroid_dcp(v);
}
void solve(){
    fill(f, f + 1 + k, INF);
    centroid_dcp(1);
    if(ans == INF)ans = -1;
}
ll best_path(ll N, ll K, ll H[][2], ll L[]){
    n = N, k = K;
    REP(i,N){
        ll u = H[i][0], v = H[i][1], w = L[i];
        u++, v++;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    solve();
    return ans;
}

#ifdef KHOA
int main(){
    ll n = 3, k = 3;
    ll H[n][2], L[n];
    REP(i,n - 1)cin>>L[i];
    REP(i,n - 1)cin>>H[i][0]>>H[i][1];
    cout<<best_path(n, k, H, L);
}
#endif

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