Submission #1355201

#TimeUsernameProblemLanguageResultExecution timeMemory
1355201chan_uuFactories (JOI14_factories)C++20
Compilation error
0 ms0 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SZ = 505050;

int dep[SZ], in[SZ], par[20][SZ], chk[SZ], N, Q;
ll pre[SZ], ans;
vector<pair<int,ll>> T[SZ], aux[SZ];

void dfs(int v) {
    static int cnt = 0;
    in[v] = ++cnt;
    for (auto[i,c] : T[v]) {
        if (i == par[0][v]) continue;
        dep[i] = dep[v]+1;
        pre[i] = pre[v] + c;
        par[0][i] = v;
        dfs(i);
    }
}

int lca(int a, int b) {
    if (dep[a] > dep[b]) swap(a, b);
    for (int i = 0; dep[b] - dep[a]; i++){
        if ((1 << i) & (dep[b] - dep[a]))
            b = par[i][b];
    }
    if (a == b) return a;
    for (int i = 19; i >= 0; i--){
        if (par[i][a] != par[i][b])
            a = par[i][a], b = par[i][b];
    }
    return par[0][a];
}

pair<ll,ll> go(int v) {
    pair<ll,ll> ret = {(ll)1e18, (ll)1e18};
    if (chk[v] == 1) ret.first = 0;
    if (chk[v] == 2) ret.second = 0;
    for (auto[i,c] : aux[v]) {
        auto[a,b] = go(i);
        ret.first = min(ret.first, a+c);
        ret.second = min(ret.second, b+c);
    }
    ans = min(ans, ret.first+ret.second);
    return ret;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);

    cin >> N >> Q;
    for (int i = 1,u,v,c; i < N; i++){
        cin >> u >> v >> c;
        u++, v++;
        T[u].emplace_back(v,c);
        T[v].emplace_back(u,c);
    }
    dfs(1);
    for (int i = 1; i < 20; i++){
        for (int j = 1; j <= N; j++)
            par[i][j] = par[i-1][par[i-1][j]];
    }
    while (Q--) {
        int s, t;
        cin >> s >> t;
        vector<int> V;
        for (int i = 1,x; i <= s; i++){
            cin >> x;
            chk[++x] = 1;
            V.push_back(x);
        }
        for (int i = 1,y; i <= t; i++) {
            cin >> y;
            chk[++y] = 2;
            V.push_back(y);
        }
        sort(V.begin(), V.end(), [&](int a, int b) { return in[a] < in[b]; });
        for (int i = 1; i < s+t; i++)
            V.push_back(lca(V[i], V[i-1]));
        sort(V.begin(), V.end(), [&](int a, int b){ return in[a] < in[b]; });
        V.erase(unique(V.begin(), V.end()), V.end());
        for (int i = 1; i < V.size(); i++){
            int p = lca(V[i], V[i-1]);
            aux[p].emplace_back(V[i], pre[V[i]] - pre[p]);
        }
        ans = 1e18;
        go(V[0]);
        cout << ans << '\n';

        for (int i : V){
            chk[i] = 0;
            aux[i].clear();
        }
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccC06fau.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccr4XqbE.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccC06fau.o: in function `main':
grader.cpp:(.text.startup+0x3b0): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x43b): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status