Submission #1116953

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1116953	2024-11-22T16:17:55 Z	ducanh0811	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KB

race

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

#define MAX_N 200005

vector<pair<int, int>> g[MAX_N];

int n, k;

int sz[MAX_N];

bool del[MAX_N];

int mp[MAX_N * 5];

int vi[MAX_N * 5];

int id = 0;

void calc(int u, int p){
    sz[u] = 1;
    for (pair<int, int> x : g[u]){
        int v, w; tie(v, w) = x;
        if (v == p || del[v]) continue;
        calc(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p, int SZ){
    for (pair<int, int> x : g[u]){
        int v, w; tie(v, w) = x;
        if (v == p || del[v]) continue;
        if (sz[v] > SZ) return centroid(v, u, SZ);
    }
    return u;
}

vector<pair<int, int>> tmp;

int res = 1e18;

void DFS(int u, int p, int W, int dep){
    if (W > k) return;
    tmp.push_back({W, dep});
    if (W == k || (mp[k - W] && vi[k - W] == id)){
        res = min(res, dep + mp[k - W]);
    }
    for (pair<int,int> x : g[u]){
        int v,w; tie(v, w) = x;
        if (v == p || del[v]) continue;
        DFS(v, u, W + w, dep + 1);
    }
}

void process(int c){

    id++;

    for (pair<int, int> x : g[c]){
        int v, w; tie(v, w) = x;

        if (del[v]) continue;

        DFS(v, c, w, 1);
        for (pair<int, int> y : tmp){
            if (!mp[y.first] || vi[y.first] != id){
                vi[y.first] = id;
                mp[y.first] = y.second;
            } else {
                mp[y.first] = min(mp[y.first], y.second);
            }

            tmp.clear();
        }
    }

}

void decompose(int u){
    calc(u, 0);
    int c = centroid(u, 0, sz[u] / 2);
    process(c);
    del[c] = true;
    for (pair<int,int> x : g[c]){
        int v, w; tie(v, w) = x;
        if (del[v]) continue;
        decompose(v);
    }
}

void solve(){
    cin >> n >> k;
    for (int i = 1; i < n; ++i){
        int u, v, l; cin >> u >> v >> l;
        u++; v++;
        g[u].push_back({v, l});
        g[v].push_back({u, l});
    }
    decompose(1);
    if (res > 1e17) res = -1;
    cout << res;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    solve();
    return 0;
}

Compilation message

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