Submission #854868

#	Time	Username	Problem	Language	Result	Execution time	Memory
854868		vjudge1	Race (IOI11_race)	C++14	100 / 100	423 ms	59112 KiB

race

#include <bits/stdc++.h>
#include <race.h>
using namespace std;
#define task ""

const int MAX = 200000;
int n, k;
int h[MAX];
long long dep[MAX];
int sz[MAX], heavy[MAX];
vector<pair<int, int>> adj[MAX];

void dfsSZ(int u, int p) {
    sz[u] = 1; heavy[u] = -1;
    for (pair<int, int> &e: adj[u]) if (e.first != p) {
        int v = e.first, w = e.second;
        dep[v] = dep[u] + w;
        h[v] = h[u] + 1;
        dfsSZ(v, u);
        sz[u] += sz[v];
        if (heavy[u] == -1 || sz[heavy[u]] < sz[v]) heavy[u] = v;
    }
}

multiset<pair<long long, int>> dp; int res;
vector<int> node;

void upd(int u, int p, int lca) {
    if (lca == -1) dp.erase(dp.find(make_pair(dep[u], h[u])));
    else {
        long long value = k - dep[u] + 2LL * dep[lca];
        auto it = dp.lower_bound(make_pair(value, 0));
        if (it != dp.end() && (*it).first == value) {
            res = min(res,
                      h[u] + (*it).second - 2 * h[lca]);
        }
        node.push_back(u);
    }
    for (pair<int, int> &e: adj[u]) if (e.first != p) {
        upd(e.first, u, lca);
    }
}


void dfs(int u, int p) {
    for (pair<int, int> &e: adj[u]) if (e.first != p && e.first != heavy[u]) {
        dfs(e.first, u);
        upd(e.first, u, -1);
    }
    if (heavy[u] > -1) {
        dfs(heavy[u], u);
        for (pair<int, int> &e: adj[u]) if (e.first != p && e.first != heavy[u]) {
            upd(e.first, u, u);
            while (node.size()) {
                int uu = node.back(); node.pop_back();
                dp.insert(make_pair(dep[uu], h[uu]));
            }
        }
    }
    long long value = dep[u] + k;
    auto it = dp.lower_bound(make_pair(value, 0));
    if (it != dp.end() && (*it).first == value) {
        res = min(res, (*it).second - h[u]);
    }
    dp.insert(make_pair(dep[u], h[u]));
}

int best_path(int N, int K, int H[][2], int L[]) {
    res = N;
    n = N;
    k = K;
    for (int i = 0; i < N - 1; ++i) {
        adj[H[i][0]].push_back(make_pair(H[i][1], L[i]));
        adj[H[i][1]].push_back(make_pair(H[i][0], L[i]));
    }
    dfsSZ(0, -1);
    dfs(0, -1);
    return res == n ? -1 : res;
}

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