Submission #1061772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061772		mnasser02	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef tuple<int, int, int> iii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LSOne(S) ((S) & -(S))

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T>
bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T>
bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll K;
int ans = 1e9;

void solve() {
    int n;
    cin >> n >> K;
    vector<vii> AL(n);
    vector<array<int, 3>> EL;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        EL.push_back({u, v});
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> EL[i][2];
    }
    for (auto [u, v, w] : EL) {
        AL[u].push_back({v, w});
        AL[v].push_back({u, w});
    }

    auto dfs = [&](auto self, int u, int p, int d, ll s) -> map<ll, int> {
        map<ll, int> res;
        res[s] = d;
        ll targ = K + 2 * s;
        for (auto [v, w] : AL[u]) {
            if (v == p) continue;
            auto cur = self(self, v, u, d + 1, s + w);
            if (res.size() < cur.size()) swap(res, cur);
            for (auto [k, v] : cur) {
                if (res.count(targ - k)) ckmin(ans, v + res[targ - k] - 2 * d);
            }
            for (auto [k, v] : cur) {
                if (res.count(k))
                    ckmin(res[k], v);
                else
                    res[k] = v;
            }
        }
        return res;
    };
    dfs(dfs, 0, -1, 0, 0);
    cout << (ans == 1e9 ? -1 : ans) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int tc = 1;
    // cin >> tc;

    while (tc--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

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