Submission #671657

#	Time	Username	Problem	Language	Result	Execution time	Memory
671657		shrimb	Race (IOI11_race)	C++17	100 / 100	393 ms	88188 KiB

race

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

using namespace std;

const int maxn = 200001;

vector<pair<int,int>> adj[maxn];

int sub[maxn];

int k;

map<long long,int> maps[maxn];

void Check (int cur, int x, int y, int& ret, int dep2, int dep) {
    if (maps[cur] . count(k + 2 * dep - x)) {
        ret = min(ret, y + (maps[cur])[k + 2 * dep - x] - 2 * dep2);
    }
}

void Insert (int cur, int x, int y) {
    if (maps[cur] . count(x)) (maps[cur])[x] = min((maps[cur])[x], y);
    else (maps[cur])[x] = y;
}

int dfs (int cur, int par, int dep, int dep2) { // dep = sum of weights // dep2 = number of edges from root
    sub[cur] = 1;
    if ((adj[cur].empty()) || (adj[cur].size() == 1 and cur != 0)) {
        // maps[cur] = new map<long long, int>();
        maps[cur] . insert({dep, dep2});
        return INT_MAX;
    }

    int mx = -1;
    int ret = INT_MAX;

    for (auto [i, j] : adj[cur]) {
        if (i != par) {
            ret = min(ret, dfs(i, cur, dep + j, dep2 + 1));
            sub[cur] += sub[i];
            if (mx == -1 || sub[i] > sub[mx]) mx = i;
        }
    }

    // maps[cur] = maps[mx];
    swap(maps[cur], maps[mx]);


    for (auto [i, j] : adj[cur]) {
        if (i != par and i != mx) {
            for (auto [x, y] : maps[i]) {
                Check(cur, x, y, ret, dep2, dep);
            }
            for (auto [x, y] : maps[i]) {
                Insert(cur, x, y);
            }
        }
    }
    Check(cur, dep, dep2, ret, dep2, dep);
    Insert(cur, dep, dep2);
    return ret;
}

int best_path(int N, int K, int H[][2], int L[]) {
    k = K;

    for (int i = 0 ; i < N - 1 ; i++) {
        auto [u, v] = H[i];
        int w = L[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }

    int ans;

    return (ans = dfs(0, 0, 0, 0)) == INT_MAX ? -1 : ans;
}

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