Submission #890385

#	Time	Username	Problem	Language	Result	Execution time	Memory
890385		anarch_y	Race (IOI11_race)	C++17	100 / 100	413 ms	52048 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back
 
const int maxn = 200001;
 
int N, K;
vector<int> adj[maxn];
vector<pair<int, int>> adj2[maxn];
int sub[maxn];
bool done[maxn];
 
int subtree_size(int s, int p){
    sub[s] = 1;
    for(auto u: adj[s]){
        if(u == p or done[u]) continue;
        sub[s] += subtree_size(u, s);
    }
    return sub[s];
}
 
int get_centroid(int s, int p, int num){
    for(auto u: adj[s]){
        if(u == p or done[u]) continue;
        if(2*sub[u] > num) return get_centroid(u, s, num);
    }
    return s;
}

ll ans = 1e18;
ll best[1000001];

void calc(int s, int p, bool fill, int d, int wt){
    if(wt > K) return;
    if(fill) best[wt] = min(best[wt], 1LL*d);
    else ans = min(ans, best[K-wt] + 1LL*d);
    for(auto &[u, t]: adj2[s]){
        if(u == p or done[u]) continue;
        calc(u, s, fill, d+1, wt+t);
    } 
}

void del(int s, int p, int d, int wt){
    if(wt > K) return;
    best[wt] = 1e18;
    for(auto &[u, t]: adj2[s]){
        if(u == p or done[u]) continue;
        del(u, s, d+1, wt+t);
    } 
}
 
void centroid_decomp(int s){
    int num = subtree_size(s, 0);
    int cent = get_centroid(s, 0, num);

    best[0] = 0;
    for(auto &[u, w]: adj2[cent]){
        if(done[u]) continue;
        calc(u, cent, false, 1, w);
        calc(u, cent, true, 1, w);
    }
    for(auto &[u, w]: adj2[cent]){
        if(done[u]) continue;
        del(u, cent, 1, w);
    }

    done[cent] = true;
    for(auto u: adj[cent]){
        if(!done[u]) centroid_decomp(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 a = H[i][0], b = H[i][1], w = L[i];
        a++; b++;
        adj[a].pb(b); adj[b].pb(a);
        adj2[a].pb({b, w}); adj2[b].pb({a, w});
    }
    fill(best, best+K+1, 1e18);
    centroid_decomp(1);
    if(ans == 1e18) ans = -1;
    return ans;
}

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