Submission #1205764

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

race

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

const int MAXN=2e5+1;
const int MAXK=1e6+1;
int n, k, u, v, w, sz[MAXN], dp[MAXK], ans=MAXN;
bool isCentroid[MAXN];
vector<array<int, 2> > a[MAXN];
unordered_set<int>W;

void DFS(int u, int p)
{
    sz[u]=1;
    for (auto it:a[u]){
        int v=it[0];
        if(v==p or isCentroid[v]) continue;
        DFS(v, u);
        sz[u]+=sz[v];
    }
}

int findCentroid(int u, int p, int treeSz)
{
    for (auto it:a[u]){
        int v=it[0];
        if(v!=p and !isCentroid[v] and sz[v]>treeSz/2){
            return findCentroid(v, u, treeSz);
        }
    }
    return u;
}

void calc(int u, int p, int h, int cur_w)
{
    if(cur_w<=k){
        if(dp[k-cur_w]!=MAXN) ans=min(ans, h+dp[k-cur_w]);
    }
    else return;
    W.insert(cur_w);
    for (auto it:a[u]){
        int v=it[0], w=it[1];
        if(v==p or isCentroid[v]) continue;
        calc(v, u, h+1, cur_w+w);
    }
}

void update(int u, int p, int h, int cur_w)
{
    if(cur_w>k) return;
    dp[cur_w]=min(dp[cur_w], h);
    for (auto it:a[u]){
        int v=it[0], w=it[1];
        if(v==p or isCentroid[v]) continue;
        update(v, u, h+1, cur_w+w);
    }
}

void build(int u)
{
    DFS(u, -1);
    int centroid=findCentroid(u, -1, sz[u]);
    isCentroid[centroid]=1;
    dp[0]=0;
    W.insert(0);
    for (auto it:a[centroid]){
        int v=it[0], w=it[1];
        if(!isCentroid[v]){
            calc(v, centroid, 1, w);
            update(v, centroid, 1, w);
        }
    }
    for (auto x:W) dp[x]=MAXN;
    for (auto it:a[centroid]){
        int v=it[0];
        if(!isCentroid[v]){
            build(v);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i=1; i<n; i++){
        cin >> u >> v >> w;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    for (int i=0; i<=k; i++){
        dp[i]=MAXN;
    }
    build(0);
    if(ans==MAXN) cout << -1;
    else cout << ans;
    return 0;
}

Compilation message (stderr)

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