Submission #942167

#	Time	Username	Problem	Language	Result	Execution time	Memory
942167		R_i_n_Nabil	경주 (Race) (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

// #include "race.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define endl '\n'
#define ll long long
#define mod 1000000007

const int N = 2e5 + 40, M = 1e6 + 9;
int n, k, ans = mod, siz[N], in[N], out[N], depth[N], flat[N], timer = 0;
ll euler[N];

vector < pair < int , int > > g[N];
bitset < N > virginity;

void dfs(int bap, int dada) {
    siz[bap] = 1;
    for(auto [cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        dfs(cld, bap);
        siz[bap] += siz[cld];
    }
}

int find(int bap, int dada, int sz) {
    for(auto [cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        if(siz[cld] > sz) return find(cld, bap, sz);
    }
    return bap;
}

void euler_tour(int bap, int dada, ll curr_val = 0, int dep = 0) {
    in[bap] = ++timer;
    flat[timer] = bap;
    euler[bap] = curr_val;
    depth[bap] = dep;
    for(auto[cld, val] : g[bap]) {
        if(cld == dada or virginity[cld]) continue;
        euler_tour(cld, bap, val + curr_val, dep + 1);
    }
    out[bap] = timer;
}

void calculate_ans(int king) {
    timer = 0;
    euler_tour(king, king);

    gp_hash_table < ll , int > gp;
    gp[0] = 0;

    for(auto[cld, val] : g[king]) {
        // Query
        for (int i = in[cld]; i <= out[cld]; i++)
        {
           // if(euler[i] > k) continue;
            int v = flat[i];
            ll need = k - euler[v];
            auto it = gp.find(need);
            if(it != gp.end()) {
                ans = min(ans, depth[v] + gp[need]);
            }
        }
        // Update
        for(int i = in[cld]; i <= out[cld]; i++) {
            //if(euler[i] > k) continue; 
            int v = flat[i];
            auto it = gp.find(euler[v]);
            if(it == gp.end()) {
                gp[euler[v]] = depth[v];
            }
            else {
                gp[euler[v]] = min(depth[v], gp[euler[v]]);
            }
        }
    }
}

void solve_sub_prob(int curr) {
    dfs(curr, curr);
    int king = find(curr, curr, siz[curr] / 2);
    virginity[king] = 1;

    calculate_ans(king);

    for(auto [cld, val] : g[king]) {
        if(virginity[cld]) continue;
        solve_sub_prob(cld);
    }

}

// int best_path(int N, int K, int H[][2], int L[])
// {
//     for (int i = 0; i < N - 1; ++i)
//     {
//         int u = H[i][0], v = H[i][1], w = L[i];
//         g[u].emplace_back(v, w), g[v].emplace_back(u, w);
//     }
//     k = K;
//     solve_sub_prob(0);

//     if(ans == mod) ans = -1;
//     return ans;
// }

void solve()
{
    cin >> n >> k;
    pair<int, int> pr[n + 9];
    for (int i = 1; i < n; i++)
    {
        cin >> pr[i].first >> pr[i].second;
    }
    for (int i = 1; i < n; i++)
    {
        int x; cin >> x;
        g[pr[i].first].push_back({pr[i].second,x});
        g[pr[i].second].push_back({pr[i].first, x});
    }
    solve_sub_prob(0);
    if (ans < mod)
        cout << ans << endl;
    else
        cout << -1 << endl;
}

int main()
{
   solve();

    return 0;
}

Compilation message (stderr)

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