Submission #1209228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209228		vache_kocharyan	Race (IOI11_race)	C++17	43 / 100	3096 ms	36740 KiB

race

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

const int INF = 1e9 + 7;
const int NN = 2e5 + 5;

vector<vector<pair<int, int>>> G;
bool used[NN];
int sz[NN];
int compSize;
int k;
int answ;

unordered_map<int, int> depth, cur_depth;

void dfs(int node, int parent) {
    sz[node] = 1;
    for (auto& [to, w] : G[node]) {
        if (to != parent && !used[to]) {
            dfs(to, node);
            sz[node] += sz[to];
        }
    }
}

int find_centroid(int node, int parent) {
    for (auto& [to, w] : G[node]) {
        if (to != parent && !used[to] && sz[to] * 2 > compSize) {
            return find_centroid(to, node);
        }
    }
    return node;
}

int get_centroid(int u) {
    dfs(u, -1);
    compSize = sz[u];
    return find_centroid(u, -1);
}

void collect_paths(int node, int parent, int depth_now, int sum_now, vector<pair<int, int>>& paths) {
    if (sum_now > k) return;
    paths.emplace_back(sum_now, depth_now);
    for (auto& [to, w] : G[node]) {
        if (to != parent && !used[to]) {
            collect_paths(to, node, depth_now + 1, sum_now + w, paths);
        }
    }
}

void process(int centroid) {
    depth.clear();
    depth[0] = 0; // Distance 0 at depth 0

    for (auto& [to, w] : G[centroid]) {
        if (used[to]) continue;

        vector<pair<int, int>> paths;
        collect_paths(to, centroid, 1, w, paths);

        for (auto& [sum, d] : paths) {
            if (depth.count(k - sum)) {
                answ = min(answ, d + depth[k - sum]);
            }
        }

        for (auto& [sum, d] : paths) {
            if (!depth.count(sum)) depth[sum] = d;
            else depth[sum] = min(depth[sum], d);
        }
    }
}

void decompose(int u) {
    int c = get_centroid(u);
    used[c] = true;
    process(c);
    for (auto& [to, w] : G[c]) {
        if (!used[to]) {
            decompose(to);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    // Reset globals
    G.clear();
    G.resize(N);
    memset(used, 0, sizeof(used));
    answ = INF;
    k = K;

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

    decompose(0);
    return (answ == INF ? -1 : answ);
}

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