Submission #672179

#	Time	Username	Problem	Language	Result	Execution time	Memory
672179		vjudge1	Race (IOI11_race)	C++17	100 / 100	380 ms	43940 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;


#define Baba_Sevawy  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ld long double
#define el '\n'
#define pi acos(-1)
#define F first
#define S second
#define sz(x) (int)(x).size()

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(gen);
}

const int NN = 2e5 + 5, M = 1e6 + 5, mod = 1e9 + 7, INF  = 2e9;
int siz[NN], k;
ll f[M];
bool vis[NN];
vector<pair<ll, ll>>adj[NN];
vector<pair<ll, ll>>all;
vector<ll>sums;
int dfs_sz(int node, int par){
    siz[node] = 1;
    for(auto i : adj[node]){
        if(i.F == par || vis[i.F]) continue;
        siz[node] += dfs_sz(i.F, node);
    }
    return siz[node];
}
int dfs_centroid(int node, int par, int n){
    for(auto i : adj[node])
        if(i.F != par && !vis[i.F] && siz[i.F] > n / 2) return dfs_centroid(i.F, node, n);
    return node;
}
void dfs_collect(int node, int par, int len, ll sum){
    all.emplace_back(len, sum);
    sums.emplace_back(sum);
    for(auto i : adj[node]){
        if(vis[i.F] || i.F == par) continue;
        dfs_collect(i.F, node, len + 1, sum + i.S);
    }
}
ll build(int node, int par){
    int size = dfs_sz(node, par);
    int centroid = dfs_centroid(node, par, size);
    if(par == -1) par = centroid;
    vis[centroid] = true;
    ll ans = 1e9;
    f[0] = 0;
    for(auto i : adj[centroid]){
        if(vis[i.F]) continue;
        all.clear();
        dfs_collect(i.F, centroid, 1, i.S);
        for(auto j : all)
            if(j.S <= k && f[k - j.S] != -1)
                ans = min(ans, j.F + f[k - j.S]);

        for(auto j : all) {
            if(j.S >= M) continue;
            if (f[j.S] == -1) f[j.S] = j.F;
            else f[j.S] = min(f[j.S], j.F);
        }
    }
    for(auto &i : sums) if(i < M) f[i] = -1;
    sums.clear();
    for(auto i : adj[centroid]){
        if(vis[i.F]) continue;
        ans = min(ans, build(i.F, centroid));
    }
    return ans;
}
int best_path(int N, int K, int H[][2], int L[]){
    for(int i = 0; i < N - 1; i++){
        H[i][0]++, H[i][1]++;
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    k = K;
    ::memset(f, -1, sizeof f);
    ll ret = build(1, -1);
    return (ret == 1e9 ? -1 : ret);
}

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