Submission #1204101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204101		henrlly	Race (IOI11_race)	C++20	0 / 100	7 ms	14400 KiB

race

#include <bits/stdc++.h>
#include <climits>
#include <vector>

using namespace std;

#define ll long long

using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;

// we need to the shortest path with weights that sum to k
const int MAXN = 2e5+1;
vector<tuple<int,int>> v[MAXN];
ll height[MAXN], sum[MAXN]; // of each node, from root, 0 at root
map<ll, ll> info[MAXN]; // info[node] is a map of sum: height of all nodes in subtree of node (incl)
ll ans = INT_MAX;
int k;

void precomp(int c, int p=-1, int cs=0, int ch=0) {
    height[c] = ch;
    sum[c] = cs;
    info[c][cs] = ch;
    for (auto [vv, w]: v[c]) {
        if (vv != p) precomp(vv, c, cs+w, ch+1);
    }
}

void merge(int c, int p=-1) {
    ll target = k + 2 * sum[c];
    for (auto [vv, w]: v[c]) {
        if (vv == p) continue;
        merge(vv, c);
        if (info[vv].size() > info[c].size()) swap(info[vv], info[c]);
        for (auto [s, h]: info[vv]) {
            if (info[c].find(target - s) != info[c].end()) {
                ans = min(ans, info[c][target - s] + h - 2 * sum[c]);
            }
        }
        for (auto [s, h]: info[vv]) {
            if (info[c].find(s) != info[c].end()) {
                info[c][s] = min(info[c][s], h);
            } else {
                info[c][s] = h;
            }
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N-1; i++) {
        v[H[i][0]].push_back({H[i][1], L[i]});
        v[H[i][1]].push_back({H[i][0], L[i]});
    }
    k = K;
    precomp(0);
    merge(0);
    return ans == INT_MAX ? -1 : ans;
}

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