Submission #1210724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210724		Born_To_Laugh	Race (IOI11_race)	C++17	43 / 100	676 ms	89372 KiB

race

#include <vector>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;

const int maxn = 200005;
int n;
long long k;
const int INF = 1e9 + 7;
int ans = INF;

vector<int> sz(maxn, 1), bigchild(maxn, -1), dep(maxn, 0);
vector<long long> dist(maxn, 0);
vector<int> adj[maxn];
map<pair<int, int>, long long> wei;

void pre_dfs(int a, int par) {
    for (auto &elm : adj[a]) {
        if (elm == par) continue;
        dep[elm] = dep[a] + 1;
        dist[elm] = dist[a] + wei[{a, elm}];
        pre_dfs(elm, a);
        sz[a] += sz[elm];
        if (bigchild[a] == -1 || sz[bigchild[a]] < sz[elm])
            bigchild[a] = elm;
    }
}

void add(int a, int par, bool godown, long long distlca, int deplca, map<long long, int>& mp) {
    long long dist1 = k + 2 * distlca - dist[a];
    if (dist1 >= 0) {
        auto it = mp.find(dist1);
        if (it != mp.end()) {
            ans = min(ans, it->second + dep[a] - 2 * deplca);
        }
    }

    auto it2 = mp.find(dist[a]);
    if (it2 == mp.end()) {
        mp[dist[a]] = dep[a];
    } else {
        if (dep[a] < it2->second) {
            mp[dist[a]] = dep[a];
        }
    }

    if (!godown) return;

    for (auto &elm : adj[a]) {
        if (elm == par) continue;
        add(elm, a, true, distlca, deplca, mp);
    }
}

void dfs(int a, int par, bool keep, map<long long, int>& mp) {
    for (auto &elm : adj[a]) {
        if (elm == par || elm == bigchild[a]) continue;
        map<long long, int> temp_mp;
        dfs(elm, a, false, temp_mp);
    }

    map<long long, int>* bigchild_mp = &mp;
    if (bigchild[a] != -1) {
        dfs(bigchild[a], a, true, mp);
    }

    add(a, par, false, dist[a], dep[a], mp);

    for (auto &elm : adj[a]) {
        if (elm == par || elm == bigchild[a]) continue;
        add(elm, a, true, dist[a], dep[a], mp);
    }

    if (!keep) {
        mp.clear();
    }
}

signed best_path(signed N, signed K, signed H[][2], signed L[]) {
    n = N;
    k = (long long)K;
    ans = INF;
    wei.clear();

    for (int i = 0; i < maxn; ++i) {
        adj[i].clear();
        sz[i] = 1;
        bigchild[i] = -1;
        dep[i] = 0;
        dist[i] = 0;
    }

    for (int i = 0; i < n - 1; ++i) {
        int x = H[i][0], y = H[i][1];
        long long w = L[i];
        adj[x].push_back(y);
        adj[y].push_back(x);
        wei[{x, y}] = w;
        wei[{y, x}] = w;
    }

    pre_dfs(0, -1);
    map<long long, int> mp;
    dfs(0, -1, true, mp);

    return (ans == INF) ? -1 : ans;
}

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