Submission #672105

#	Time	Username	Problem	Language	Result	Execution time	Memory
672105		vjudge1	Race (IOI11_race)	C++17	100 / 100	381 ms	56460 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second


const ll M = 1e6 + 5;
int k, sz[M];
vector<pii> adj[M];
vector<pair<int, ll>> pool;
vector<ll> vals;
bool vis[M];
int dp[M];
ll ans;

int dfsSz(int u, int par) {
    sz[u] = 1;
    for (auto v: adj[u]) {
        if (v.fi == par || vis[v.fi])continue;
        dfsSz(v.fi, u);
        sz[u] += sz[v.fi];
    }
    return sz[u];
}

int dfsCenter(int u, int par, int size) {
    for (auto v: adj[u]) {
        if (v.fi == par || vis[v.fi])continue;
        if (sz[v.fi] * 2 > size)
            return dfsCenter(v.fi, u, size);
    }
    return u;
}

void collect(int u, int par, ll sum, int dep) {
    pool.emplace_back(sum, dep);
    vals.push_back(sum);
    for (auto v: adj[u]) {
        if (v.fi == par || vis[v.fi])continue;
        collect(v.fi, u, sum + v.se, dep + 1);
    }
}

void build(int u, int par) {
    int size = dfsSz(u, par);
    int centroid = dfsCenter(u, par, size);
    if (par == -1)
        par = centroid;
    vis[centroid] = true;
    for (auto v: adj[centroid]) {
        if (v.fi == par || vis[v.fi])continue;
        pool.clear();
        collect(v.first, centroid, v.se, 1);
        for (auto &i: pool) {
            if (i.first > k)continue;
            ans = min(ans, dp[k - i.first] + i.second);
        }
        for (auto &i: pool) {
            if (i.first > k)continue;
            dp[i.first] = min(1ll * dp[i.first], i.second);
        }
    }
    for (long long val: vals) {
        if (val > k)continue;
        dp[val] = 1e9;
    }
    vals.clear();
    for (auto v: adj[centroid]) {
        if (v.fi == par || vis[v.fi])continue;
        build(v.fi, centroid);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 1; i < M; ++i) {
        dp[i] = 1e9;
    }
    ans = 1e9;
    for (int i = 0; i < N - 1; ++i) {
        int u = H[i][0] - 1;
        int v = H[i][1] - 1;
        adj[u].emplace_back(v,L[i]);
        adj[v].emplace_back(u,L[i]);
    }
    k = K;
    build(0,0);
    if(ans == 1e9){
        ans = -1;
    }
    return ans;
}

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