Submission #1084826

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1084826	2024-09-07T04:42:52 Z	vjudge1	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll N = 2e5 + 10;
vector<array<ll, 2>> ad[N];
ll mark[N], sz[N], ans = 1e18, k;
array<ll, 2> nodes[N];
int t, tin[N], tout[N], lv[N];
unordered_map <ll, ll> we;

ll size(ll node, ll par) {
    sz[node] = 1;
    for (auto [v, w] : ad[node]) {
        if (v != par and !mark[v]) {
            sz[node] += size(v, node);
        }
    }
    return sz[node];
}

ll centroid(ll node, ll par, ll s) {
    for (auto [v, w] : ad[node]) {
        if (v != par and !mark[v]) {
            if (sz[v] > s / 2) return centroid(v, node, s);
        }
    }
    return node;
}
void dfs(ll node, ll par, ll wt, int l = 0) {
    nodes[t] = {node, wt};
    tin[node] = t++;
    lv[node] = l;
    for (auto [v, w] : ad[node]) {
        if (v != par and !mark[v]) {
            dfs(v, node, wt + w, l + 1);
        }
    }
    tout[node] = t - 1;
}

void go(ll node) {
    ll s = size(node, node);
    ll c = centroid(node, node, s);
    mark[c] = 1;
    t = 0;
    dfs(c, c, 0);

    for (int i = 0; i < t; i++) {
        auto [a, b] = nodes[i];
        we[b] = 1e18;
    }
    we[0] = 0;
    for (auto [v, w] : ad[c]) {
        if (!mark[v]) {
            for (ll i = tin[v]; i <= tout[v]; i++) {
                auto [a, b] = nodes[i];
                auto it = we.find(k - b);
                if (k - b >= 0 and it != we.end())
                    ans = min(ans, (*it).second + lv[a]);
            }
            for (ll i = tin[v]; i <= tout[v]; i++) {
                auto [a, b] = nodes[i];
                we[b] = min(we[b], 1ll * lv[a]);
            }
        }
    }
    for (int i = 0; i < t; i++) {
        auto [a, b] = nodes[i];
        we[b] = 1e18;
    }

    for (auto [v, w] : ad[c]) {
        if (!mark[v]) {
            go(v);
        }
    }
}

int best_path(int n, int d, int H[][2], int dis[]) {
    k = d;
    for (int i = 0; i + 1 < n; i++) {
        ad[H[i][0]].push_back({H[i][1], dis[i]});
        ad[H[i][1]].push_back({H[i][0], dis[i]});
    }
    go(0);
    if (ans == 1e18) ans = -1;
    return ans;
}


void solve() {
    int n, k; cin >> n >> k;
    int arr[n - 1][2];
    for (int i = 0; i + 1 < n; i++) {
        cin >> arr[i][0] >> arr[i][1];
    }
    int dis[n - 1];
    for (int i = 0; i + 1 < n; i++) {
        cin >> dis[i];
    }
    cout << best_path(n, k, arr, dis) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll tt = 1;
    // cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

/usr/bin/ld: /tmp/ccmOt560.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccS02h11.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status