Submission #525816

#	Time	Username	Problem	Language	Result	Execution time	Memory
525816		gg123_pe	Race (IOI11_race)	C++17	100 / 100	559 ms	63864 KiB

race

#include <bits/stdc++.h> 
#include "race.h" 
using namespace std; 

typedef long long ll; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define ff first
#define ss second

const ll N = 1e6 + 5; 

ll n, k, sz[N], ans = N, dist[N], dreal[N], aux[N]; 
bool on[N]; 
vector <pair<int,ll>> adj[N]; 
vector <int> ra; 

int size(int u, int f){
    sz[u] = 1;
    for(auto v: adj[u]) if(v.first != f and !on[v.first]) sz[u] += size(v.first, u); 
    return sz[u]; 
}
int get_centroid(int u, int f, int curr_size){
    for(auto v: adj[u]) if(v.first != f and !on[v.first] and sz[v.first]*2 > curr_size) return get_centroid(v.first, u, curr_size);
    return u; 
}
void get_tree(int u, int f){
    ra.push_back(u); 
    for(auto v: adj[u]) if(v.first != f and !on[v.first]) get_tree(v.first, u); 
}
void dfs(int u, int f){
    for(auto p: adj[u]){
        ll v = p.first, w = p.second; 
        if(v == f or on[v]) continue; 
        dist[v] = dist[u] + 1; 
        dreal[v] = dreal[u] + w; 
        dfs(v, u); 
    }
}
void solve(int u, int f){
    int cen = get_centroid(u, f, size(u, f)); 

    on[cen] = 1, dist[cen] = dreal[cen] = 0; 
    dfs(cen, f); 

    vector <ll> AUX; 
    for(auto p: adj[cen]){
        int v = p.ff; 
        if(v == f or on[v]) continue; 
        ra.clear(); get_tree(v, cen); 
        for(int x: ra){
            if(dreal[x] == k){
                ans = min(ans, dist[x]);
            }
            else if(dreal[x] > k) continue; 
            ans = min(ans, aux[k-dreal[x]] + dist[x]); 
        }
        for(int x: ra){
            if(dreal[x] >= k) continue; 
            aux[dreal[x]] = min(aux[dreal[x]], dist[x]); 
            AUX.push_back(dreal[x]); 
        }
    }
    for(int x: AUX) aux[x] = N; 
    for(auto v: adj[cen]) if(v.first != f and !on[v.first]) solve(v.first, cen);
}
int best_path(int m, int K, int H[][2], int L[]){
    n = m, k = K; 
    f(i,0,n-1){
        ll u = H[i][0], v = H[i][1], w = L[i]; 
        adj[u].push_back({v, w}); 
        adj[v].push_back({u, w}); 
    }
    f(i,0,N) aux[i] = N; 
    solve(0, -1);
    if(ans == N) ans = -1; 
    return ans; 
}

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