Submission #1255065

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

race

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,MOD=1e9+7;
#define ll long long
#define yes {cout<<"YES";return;}
#define no {cout<<"NO";return;}
#define srt(a,n) sort(a+1,a+n+1);
#define srt2(a,n,comp) sort(a+1,a+n+1,comp);
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define MAXN 1000005
const ll L=1e18;
int n,k;
vector <pair <int,int>> s[N];
int sz[N],high[N],dist[N],par[N];
bool visited[N];
int exist[MAXN];
int Save[MAXN];
int thutu = 0;
vector <pair <int,int>> tmp;
int res = 1e9;
int dfs(int i, int pre){
    sz[i] = 1;
    for (auto x: s[i]){
        if (x.fi == pre || visited[x.fi])
            continue;
        dist[x.fi] = dist[i] + x.se;
        sz[i] += dfs(x.fi,i);
    }
    return sz[i];
}
int Find_Centroid(int i, int pre, int Size){
    for (auto x: s[i]){
        if (x.fi == pre || visited[x.fi])
            continue;
        if (sz[x.fi] > Size/2)
            return Find_Centroid(x.fi,i,Size);
    }
    return i;
}
int dfs2(int i, int pre, int cnt, int d, int l){
    int ans = 1e9;
    if (d <= k && exist[k - d] == cnt){
        ans = min(ans, l + Save[k-d]);
    }
    if (d <= k){
        tmp.pb({d,l});
        for (auto x: s[i]){
            if (visited[x.fi] || x.fi == pre)
                continue;
            ans = min(ans, dfs2(x.fi,i,cnt,d + x.se,l + 1));
        }
    }
    return ans;
}
void Build_Centroid(int u,int p){
    int cnt = ++thutu;
    int Size = dfs(u,u);
    int centroid = Find_Centroid(u,u,Size);
    visited[centroid] = true;
    exist[0] = cnt;
    Save[0] = 0;
    for (auto x: s[centroid]){
        if (visited[x.fi])
            continue;
        tmp.clear();
       res = min(res, dfs2(x.fi,centroid,cnt,x.se,1));
        for (auto v: tmp){
            int i = v.fi;
            int j = v.se;
            if (exist[i] < cnt){
                exist[i] = cnt;
                Save[i] = j;
            }
            if (Save[i] > j)
                Save[i] = j;
        }
    }
    visited[centroid] = true;
    for (auto x: s[centroid]){
        if (visited[x.fi])
            continue;
        Build_Centroid(x.fi,u);
    }
}
void solve()
{
    cin>>n>>k;
    for (int i = 1;i < n;i++){
        int u,v,l;
        cin>>u>>v>>l;
        s[u].pb({v,l});
        s[v].pb({u,l});
    }
    Build_Centroid(1,0);
    if (res == 1e9)
        cout<<-1;
    else cout<<res;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    solve();
    return 0;
}

Compilation message (stderr)

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