Submission #1292178

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292178		tab1540	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

long long n, m;
vector<pair<int, int>> graph[200009];

long long prefix[200009];

int node2disc[200009];
int disc2node[400009];
int disc2dept[400009];
int cnt = 0;
void dfs1(int a, int par, int dept) {
    node2disc[a] = ++cnt;
    disc2node[cnt] = a;
    disc2dept[cnt] = dept;

    for (pair<int, int> x : graph[a]) {
        if (x.first == par) continue;

        prefix[x.first] = prefix[a] + x.second;
        dfs1(x.first, a, dept + 1);
        disc2node[cnt] = a;
        disc2dept[cnt] = dept;
    }
    cnt++;
}
pair<int, int> rmmq[400009][19];
void build_rmq() {
    for (int i = 1; i < cnt; i++) {
        rmmq[i][0] = {disc2dept[i], i};
        for (int j = 0; (1 << (j + 1)) <= i; j++) {
            rmmq[i][j + 1] = min(rmmq[i - (1 << j)][j], rmmq[i][j]);
        }
    }
}
pair<int, int> get_rmq(int u, int v) {
    if (u == v) return rmmq[u][0];
    if (u > v) swap(u, v);
    int lg = 31 - __builtin_clz(v - u + 1);
    return min(
        rmmq[u + (1 << lg) - 1][lg],
        rmmq[v][lg]
    );
}
int get_lca(int u, int v) {
    return disc2node[get_rmq(node2disc[u], node2disc[v]).second];
}
int calc_dist(int u, int v) {
    return prefix[u] + prefix[v] - (2 * prefix[get_lca(u, v)]);
}
int calc_cnt_dist(int u, int v) {
    return disc2dept[node2disc[u]] + disc2dept[node2disc[v]] - (2 * get_rmq(node2disc[u], node2disc[v]).first);
}

int centroid_parent[200009] = {};

bool blocked[200009] = {};

int get_tree_size(int a, int par) {
    int sum = 1;
    for (pair<int, int> x : graph[a]) {
        if (x.first == par|| blocked[x.first]) continue;
        sum += get_tree_size(x.first, a);
    }
    return sum;
}

int get_centroid(int a, int par, int size) {
    int sum = 1;
    for (pair<int, int> x : graph[a]) {
        if (x.first == par || blocked[x.first]) continue;
        int ehe = get_centroid(x.first, a, size);
        if (ehe < 0) return ehe;
        sum += ehe;
    }
    if (sum > size / 2) return -a;
    return sum;
}

int build_centroid_tree(int a) {
    int centroid = -get_centroid(a, a, get_tree_size(a, a));
    // cout << a << " = " << centroid << " " << get_tree_size(a, a) << endl;

    blocked[centroid] = 1;

    for (pair<int, int> x : graph[centroid]) {
        if (blocked[x.first]) continue;

        int ch = build_centroid_tree(x.first);
        centroid_parent[ch] = centroid;
        // cout << ch << " " << centroid << endl;
    }
    return centroid;
}

map<long long, int> dist_to_child[200009];

int ans = 1 << 30;

void query(int a) {
    int gay = a;
    while (gay > 0) {
        int dist = calc_dist(gay, a);
        int cnt = calc_cnt_dist(gay, a);

        if (dist_to_child[gay].find(m - dist) != dist_to_child[gay].end()) {
            ans = min(ans, dist_to_child[gay][m - dist] + cnt);
        }

        if (dist_to_child[gay].find(dist) == dist_to_child[gay].end()) {
            dist_to_child[gay][dist] = cnt;
        } else {
            dist_to_child[gay][dist] = min(dist_to_child[gay][dist], cnt);
        }

        gay = centroid_parent[gay];
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie();

    cin >> n >> m;

    for (int i = 1; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        x++;
        y++;

        graph[x].push_back({y, z});
        graph[y].push_back({x, z});
    }

    dfs1(1, 1, 1);
    build_rmq();
    build_centroid_tree(1);

    for (int i = 1; i <= n; i++) {
        query(i);
    }  

    if (ans == 1 << 30) {
        cout << -1;
        return 0;
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccfVyx0m.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc7jQWnX.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccfVyx0m.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status