Submission #824456

#	Time	Username	Problem	Language	Result	Execution time	Memory
824456		Koyote	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 2;
const ll LINF = 1e18;

int n, subtree_size[MAXN];
vector<pair<int, ll>> adj[MAXN], ancestors[MAXN];
bitset<MAXN> removed;
ll min_dist_from_source[MAXN];

int dfs_subtree_size(int u, int p, ll depth, int anc) {
    subtree_size[u] = 1;
    if (anc != -1) ancestors[u].emplace_back(anc, depth);
    for (auto v : adj[u]) if (!removed[v.first] && v.first != p)
        subtree_size[u] += dfs_subtree_size(v.first, u, depth + v.second, anc);
    return subtree_size[u];
}

int find_centroid(int u, int p, int subt_sz) {
    for (auto v : adj[u]) if (!removed[v.first] && v.first != p && subtree_size[v.first] > subt_sz / 2)
        return find_centroid(v.first, u, subt_sz);
    return u;
}

void centroid_decompose(int u) {
    int c = find_centroid(u, -1, subtree_size[u]);
    removed[c] = 1;
    for (auto v : adj[c]) if (!removed[v.first])
        dfs_subtree_size(v.first, -1, v.second, c);
    for (auto v : adj[c]) if (!removed[v.first])
        centroid_decompose(v.first);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n; i++) min_dist_from_source[i] = LINF;
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }

    dfs_subtree_size(0, -1, 0, -1);
    centroid_decompose(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll res = LINF;
    for (int i = 0; i < S; i++) {
        int u = X[i]; min_dist_from_source[u] = 0;
        for (auto v : ancestors[u])
            min_dist_from_source[v.first] = min(min_dist_from_source[v.first], v.second);
    }
    for (int i = 0; i < T; i++) {
        int u = Y[i];
        res = min(res, min_dist_from_source[u]);
        for (auto v : ancestors[u])
            res = min(res, min_dist_from_source[v.first] + v.second);
    }
    for (int i = 0; i < S; i++) {
        int u = X[i]; min_dist_from_source[u] = LINF;
        for (auto v : ancestors[u])
            min_dist_from_source[v.first] = LINF;
    }
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int N, Q; cin >> N >> Q;
    int A[N], B[N], D[N];
    for (int i = 0; i < N - 1; i++) cin >> A[i] >> B[i] >> D[i];
    Init(N, A, B, D);
    int S, T;
    while (Q--) {
        cin >> S >> T;
        int X[S], Y[T];
        for (int i = 0; i < S; i++) cin >> X[i];
        for (int i = 0; i < T; i++) cin >> Y[i];
        cout << Query(S, X, T, Y) << '\n';
    }
}

Compilation message (stderr)

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