Submission #640896

#	Time	Username	Problem	Language	Result	Execution time	Memory
640896		berarchegas	Race (IOI11_race)	C++17	100 / 100	565 ms	33728 KiB

race

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

using namespace std;
using pii = pair<int, int>;

const int MAXK = 1e6 +5, MAXN = 2e5+ 5;

vector<pii> v[MAXN];
vector<int> limpa;
int dp[MAXK], vis[MAXN], sz[MAXN], ans = MAXK, k;

int subtree(int node, int pai = 0) {
    sz[node] = 1;
    for (pii x : v[node]) {
        if (!vis[x.first] && x.first != pai) {
            sz[node] += subtree(x.first, node);
        }
    }
    return sz[node];
}

int centroid(int node, int desired, int pai = 0) {
    for (pii x : v[node]) {
        if (!vis[x.first] && x.first != pai && sz[x.first] > desired) {
            return centroid(x.first, desired, node);
        }
    }
    return node;
}

void calcDP(int node, int pai, bool filling, int dep, int dist) {
    if (dist > k) return;
    if (filling) {
        dp[dist] = min(dp[dist], dep);
        if (dist)
            limpa.push_back(dist);
    }
    else {
        ans = min(ans, dep + dp[k - dist]);
    }
    for (pii x : v[node]) {
        if (x.first != pai && !vis[x.first]) {
            calcDP(x.first, node, filling, dep + 1, dist + x.second);
        }
    }
}

void solve(int node) {
    int c = centroid(node, subtree(node) / 2);
    vis[c] = true;
    for(int i = 0; i < 2; i++) {

        // do it once normally and then again reversed
        for (pii x : v[c]) {
            if (!vis[x.first]) {
                calcDP(x.first, c, false, 1, x.second);
                calcDP(x.first, c, true, 1, x.second);
            }
        }
        for (int x : limpa) dp[x] = MAXK;
        limpa.clear();
        reverse(v[c].begin(), v[c].end());
    }
    for (pii x : v[c]) {
        if (!vis[x.first]) {
            solve(x.first);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    k = K;
    for (int i = 0; i < N - 1; i++) {
        v[H[i][0]].emplace_back(H[i][1], L[i]);
        v[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    for (int i = 1; i < MAXK; i++) dp[i] = MAXK;
    solve(1);
    return (ans == MAXK ? -1 : ans);
    return N;
}

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