Submission #1244348

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

race

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include"race.h"
typedef long long ll;
#define vec vector
using namespace std;

struct Edge {
    ll to, w;
};

const ll maxn = 2e5 + 1;
const ll maxk = 1e6 + 1;
ll ans, k, t = 0;
vec<Edge> adj[maxn];
ll deleted[maxn], ofLength[maxk], s[maxn], lastUpdate[maxk];

void find_sizes(ll v, ll p = -1) {
    s[v] = 1;
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p) {
            find_sizes(e.to, v);
            s[v] += s[e.to];
        }
}

ll find_centroid(ll v, ll n, ll p = -1) {
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p && s[e.to] * 2 > n)
            return find_centroid(e.to, n, v);
    return v;
}

void use_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) {
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p)
            use_dfs(e.to, dist + e.w, dist1 + 1, v);
    if (dist > k) return;
    if (lastUpdate[k - dist] == t)
        ans = min(ans, ofLength[k - dist] + dist1);
    if (dist == k)
        ans = min(ans, dist1);
}

void apply_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) {
    for (auto &e : adj[v])
        if (!deleted[e.to] && e.to != p)
            apply_dfs(e.to, dist + e.w, dist1 + 1, v);
    if (dist > k) return;
    if (lastUpdate[dist] < t)
        ofLength[dist] = dist1;
    else
        ofLength[dist] = min(ofLength[dist], dist1);
    lastUpdate[dist] = t;
}

void divide(ll v = 0) {
    find_sizes(v);
    ll cent = find_centroid(v, s[v]);
    deleted[cent] = 1;

    t++;
    for (auto &e : adj[cent]) {
        use_dfs(e.to, e.w);
        apply_dfs(e.to, e.w);
    }

    // for (auto &l : usedLengths)
    //     ofLength[l] = 1e9;
    // usedLengths.clear();

    for (auto &e : adj[cent])
        if (!deleted[e.to])
            divide(e.to);
}

int main() {
    ll n;
    cin >> n >> k;
    // adj.assign(n, {});
    // deleted.assign(n, 0);
    // s.resize(n);
    // ofLength.assign(k + 1, 1e9);
    ans = 1e9;
    for (ll i = 0; i < n - 1; i++) {
        ll a, b, w;
        cin >> a >> b >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }
    divide();
    cout << (ans == 1e9 ? -1 : ans) << '\n';
}

// int best_path(int N, int K, int H[][2], int L[]) {
//     ll i;
//     k = K;
//     // deleted.assign(N, 0);
//     // adj.assign(N, {});
//     // s.resize(N);
//     // ofLength.assign(K + 1, 1e9);
//     fill(begin(ofLength), end(ofLength), 1e9);
//     usedLengths.reserve(1e6);
//     ans = 1e9;
//     for (i = 0; i < N - 1; i++) {
//         adj[H[i][0]].push_back({H[i][1], L[i]});
//         adj[H[i][1]].push_back({H[i][0], L[i]});
//     }
//     divide();
//     return (ans == 1e9 ? -1 : ans);
// }

Compilation message (stderr)

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