Submission #551233

#	Time	Username	Problem	Language	Result	Execution time	Memory
551233		alirezasamimi100	Race (IOI11_race)	C++17	100 / 100	1243 ms	42256 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using pll= pair<ll,ll>;
#define pb push_back
vector<pll> adj[200010];
bool hide[200010];
ll sz[200010],k,ans=1e9;
map<ll,ll> mp;
void plant(ll v , ll p = 0){
    sz[v] = 1;
    for(auto [u,w] : adj[v])
        if(u != p && !hide[u]){
            plant(u , v);
            sz[v] += sz[u];
        }
}
ll find_centroid(ll v , ll n , ll p = 0){
    bool found = 1;
    while(found){
        found = 0;
        for(auto [u,w] : adj[v])
            if(u != p && !hide[u] && sz[u] * 2 > n){
                found = 1;
                p = v;
                v = u;
                break;
            }
    }
    return v;
}
void dfs(ll v, ll x, ll h, ll p=0){
    if(x<=k && mp.count(k-x)) ans=min(ans,h+mp[k-x]);
    for(auto [u,w] : adj[v]) if(!hide[u] && u!=p) dfs(u,x+w,h+1,v);
}
void sfd(ll v, ll x, ll h, ll p=0){
    if(x<=k && (!mp.count(x) || mp[x]>h)) mp[x]=h;
    for(auto [u,w] : adj[v]) if(!hide[u] && u!=p) sfd(u,x+w,h+1,v);
}
void solve(ll v){
    plant(v);
    v = find_centroid(v , sz[v]);
    hide[v] = 1;
    mp.clear();
    mp[0]=0;
    for(auto [u,w] : adj[v]){
        if(!hide[u]){
            dfs(u,w,1);
            sfd(u,w,1);
        }
    }
    for(auto [u,w] : adj[v]) if(!hide[u]) solve(u);
}
int best_path(int N, int K, int H[][2], int L[]){
    for(ll i=0; i<N-1; i++){
        ll v=H[i][0]+1,u=H[i][1]+1;
        adj[v].pb({u,L[i]});
        adj[u].pb({v,L[i]});
    }
    k=K;
    solve(1);
    if(ans==1e9) ans=-1;
    return ans;
}

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