Submission #1317733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317733		okahak71	Race (IOI11_race)	C++20	100 / 100	590 ms	43480 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll array<ll, 2>
#define ss second
#define ff first
using namespace std;

const ll N = 2e5 + 5;
const int inf = INT_MAX;

ll ans = inf;
vector<vector<pll>>g;
ll ch[N], sz[N]; map<ll, ll>dis;

ll dfs(ll u, ll p){
    sz[u] = 1;
    for(auto &[v, W] : g[u]){
        if(v == p or ch[v]) continue;
        sz[u] += dfs(v, u);
    }
    return sz[u];
}

ll get_cent(ll u, ll p, ll mx){
    for(auto &[v, W] : g[u]){
        if(v == p or ch[v]) continue;
        if(sz[v] > mx / 2) return get_cent(v, u, mx);
    }
    return u;
}

void search(ll u, ll p, ll k, queue<pll> &nw, ll d = 0, ll W = 0){
    if(dis.count(k - W)) ans = min(ans, dis[k - W] + d);
    nw.push({d, W});
    for(auto &[v, w] : g[u]){
        if(v == p or ch[v]) continue;
        search(v, u, k, nw, d + 1, W + w);
    }
}

void get_ans(ll u, ll p, ll k){
    ll cent = get_cent(u, p, dfs(u, p));
    dis[0] = 0; queue<pll>nw;
    for(auto &[v, w] : g[cent]){
        if(ch[v]) continue;
        search(v, cent, k, nw, 1, w);
        while(!nw.empty()){
            auto [d, W] = nw.front();
            nw.pop();
            auto it = dis.find(W);
            if(it == dis.end()) dis[W] = d;
            else dis[W] = min(it->ss, d);
        }
    }
    ch[cent] = 1;
    dis.clear();
    for(auto &[v, W] : g[cent]){
        if(ch[v]) continue;
        get_ans(v, cent, k);
    }
}

int best_path(int n, int k, int h[][2], int l[]){
    g.assign(n, {});
    for(ll i = 0; i < n - 1; i++){
        auto [a, b] = h[i];
        g[a].pb({b, l[i]}), g[b].pb({a, l[i]});
    }
    get_ans(0, -1, k); return (ans == inf ? -1 : ans);
}

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