Submission #629968

#	Time	Username	Problem	Language	Result	Execution time	Memory
629968		bebra	Race (IOI11_race)	C++17	100 / 100	463 ms	96328 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

const int MAX_N = 200'000;
const int INF = 1e9;
vector<pair<int, int>> g[MAX_N];
unordered_map<long long, int> s[MAX_N];
int depth[MAX_N];
long long len[MAX_N];
int ans = INF;
int k;

template<typename T>
void merge(T& lhs, T& rhs, int v) {
    if (lhs.size() > rhs.size()) {
        swap(lhs, rhs);
    }
    for (const auto& [curr_len, curr_depth] : lhs) {
        long long need_find = k + 2 * len[v] - curr_len;
        if (rhs.find(need_find) != rhs.end()) {
            ans = min(ans, curr_depth + rhs.at(need_find) - 2 * depth[v]);
        }
    }
    for (const auto& [key, value] : lhs) {
        if (rhs.find(key) == rhs.end()) {
            rhs[key] = value;
        } else {
            rhs[key] = min(rhs[key], value);
        }
    }
}

void dfs(int v = 0, int p = -1) {
    s[v][len[v]] = depth[v];
    for (const auto& [u, weight] : g[v]) {
        if (u != p) {
            depth[u] = depth[v] + 1;
            len[u] = len[v] + weight;
            dfs(u, v);
            merge(s[u], s[v], v);
        }
    }
}

int best_path(int n, int curr_k, int highways[][2], int length[]) {
    for (int i = 0; i < n - 1; ++i) {
        auto [u, v] = highways[i];
        g[u].emplace_back(v, length[i]);
        g[v].emplace_back(u, length[i]);
    }
    k = curr_k;
    dfs();
    if (ans == INF) ans = -1;
    return ans;
}

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