Submission #1155403

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

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define li(i,a,b) for(int (i) = (a); (i)<(b); i++)
#define all(v) v.begin(), v.end()
#define mem(name, val) memset(name, val, sizeof(name))
#define endl '\n'

const int nmax = 2e5+3;
const int kmax = 1e6+3;
int n,k,ans, cnt[kmax], sz[nmax], r[nmax];
vector<pii> adj[nmax];

int dfs_sz(int v, int p = -1){
    sz[v]=1;
    for(auto [u,len] : adj[v]){
        if(u == p || r[u]) continue;
        sz[v] += dfs_sz(u,v);
    }
    return sz[v]; 
}

int get_center(int v, int ts, int p = -1){
    for(auto [u,len] : adj[v]){
        if(u == p || r[u]) continue; 
        if(sz[u] * 2 > n) return get_center(u,ts,v);
    }
    return v;
}


void get_cnt(int sum, bool filling, int u, int p = -1, int depth = 1)
{
    if(sum > k) return;
    if(filling)
        cnt[sum] = min(cnt[sum],depth);
    else {
        if(cnt[k - sum] != -1){
            if(ans == -1) ans = depth+cnt[k-sum];
            else ans = min(ans, depth+cnt[k-sum]);
        }
    }
    for(auto [v, len]: adj[u]) {
        if(v == p || r[v]) continue;
        get_cnt(sum + len, filling, v, u, depth + 1);
    }
}


void del(int sum, int u, int p = -1)
{
    if(sum > k) return;
    cnt[sum] = -1;
    for(auto [v,len]: adj[u]) {
        if(v==p || r[v]) continue;
        del(sum + len, v, u);
    }
}

void build_decomp(int v = 0){
    int center = get_center(v, dfs_sz(v));
    r[center] = 1;
    cnt[0]=0;   

    for(auto [u,len] : adj[v]){
        if(r[u]) continue;
        get_cnt(len,false,v);
        get_cnt(len,true,v);
    }

    for(auto [u,len]: adj[v]){
        if(r[v])continue;
        del(len, u);
    }

    for(auto [u,len] : adj[v]){
        if(r[u]) continue;
        build_decomp(u);
    }
}


int best_path(){
    ans = -1;
    mem(cnt,-1);
    build_decomp(0);
    return ans;
}


int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin>>n>>k;
    vector<vector<int>> h(n, vector<int>(2));
    vector<int> l(n);
    li(i,0,n-1){
        cin>>h[i][0]>>h[i][1];
    }
    li(i,0,n-1){
        cin>>l[i];
    }
    li(i,0,n-1){
        adj[h[i][0]].pb({h[i][1],l[i]});
        adj[h[i][1]].pb({h[i][0],l[i]});
    }
    cout<<best_path();
    return 0;
}

Compilation message (stderr)

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