Submission #1287927

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

race

#include <bits/stdc++.h>

using namespace std;
// #define int long long

const int MX = 2e5+1;

map<int,int> col[MX];
vector<pair<int,int>> adj[MX];
int ans = 1e9, k, n;
int w[MX];

void insert(int idx,pair<int,int> val){
    val.first += w[idx];
    val.second += 1;
    if(val.first == k){
        ans = min(ans,val.second);
    }
    if(val.first <= k){
        if(!col[idx].count(val.first)) col[idx][val.first] = val.second;
        else col[idx][val.first] = min(val.second, col[idx][val.first]);
    }
}

void init(int cur,int par){
    for(pair<int,int>& nxt:adj[cur]){
        if(nxt.first != par){
            w[nxt.first] = nxt.second;
            init(nxt.first,cur);
        }
    }
}

void dfs(int cur,int par){
    if(cur != 1){
        insert(cur,{0,0});
    }
    for(pair<int,int>& nxt:adj[cur]){
        int nx = nxt.first;
        if(nx == par) continue;
        dfs(nx,cur);
        if(col[cur].size() < col[nx].size()){
            swap(col[cur],col[nx]);
        }
        for(auto cols:col[nx]){
            int val = cols.first;
            int rem = k+w[cur] - val;
            if(col[cur].count(rem)){
                ans = min(ans,col[cur][rem]+cols.second-1);
            }
            insert(cur,cols);
        }
    }
}

vector<int> edg[MX];

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

    dfs(1,0);
    if(ans == 1e9) ans = -1;
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

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