Submission #647763

#	Time	Username	Problem	Language	Result	Execution time	Memory
647763		clams	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

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

const int N = 2e5 + 5;

int n, k;
vector<pair<int, int>> adj[N];

int sz[N], par[N];
bool vis[N];
int ans = N;

void DfsSize(int u, int p) {
    sz[u] = 1;
    for (auto& [v, w] : adj[u]) {
        if (v != p && !vis[v]) {
            DfsSize(v, u);
            sz[u] += sz[v];
        }
    }
}

int FindCentroid(int u, int p, int s) {
    for (auto& [v, w] : adj[u]) {
        if (v != p && !vis[v] && sz[v] * 2 > s) {
            return FindCentroid(v, u, s);
        }
    }
    return u;
}

map<int, int> mp;

void DfsCalc(int u, int p, bool cal, int cur, int dep) {
    if (cur > k) return;

    if (cal) {
        if (mp.count(k - cur)) {
            ans = min(ans, dep + mp[k - cur]);
        }
    } else {
        if (!mp.count(cur)) {
            mp[cur] = dep;
        }
    }

    for (auto& [v, w] : adj[u]) {
        if (v != p && !vis[v]) {
            DfsCalc(v, u, cal, cur + w, dep + 1);
        }
    }
}

void BuildCentroid(int u, int p) {
    DfsSize(u, 0);

    int c = FindCentroid(u, p, sz[u]);
    vis[c] = 1;
    par[c] = p;

    mp[0] = 0;
    for (auto& [v, w] : adj[c]) {
        if (!vis[v]) {
            DfsCalc(v, c, 1, w, 1);
            DfsCalc(v, c, 0, w, 1);      
        }
    }
    mp.clear();

    for (auto& [v, w] : adj[c]) {
        if (!vis[v]) {
            BuildCentroid(v, c);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u++, v++;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    BuildCentroid(1, 0);

    cout << (ans == N ? -1 : ans) << '\n';
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccls3axy.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccwgBaxw.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccwgBaxw.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