Submission #659960

#	Time	Username	Problem	Language	Result	Execution time	Memory
659960		zse	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KiB

factories

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>

ll ans[100000];
int N, Q;
vpii adj[500000];

int sz[500000];
bool vis[500000];
vi vX[500000];
vi vY[500000];

int getSz(int n, int p) {
    sz[n] = 1;
    for (auto &[m, d] : adj[n]) {
        if (m == p || vis[m]) continue;
        sz[n] += getSz(m, n);
    }
    return sz[n];
}

int getCent(int n, int p, int cap) {
    for (auto &[m, d] : adj[n]) {
        if (m == p || vis[m]) continue;
        if (2 * sz[m] > cap) return getCent(m, n, cap);
    }
    return n;
}

ll mX[100000];
ll mY[100000];

void dfs(int n, int p, ll d) {
    for (int &x : vX[n]) {
        mX[x] = min(mX[x], d);
        ans[x] = min(ans[x], mX[x] + mY[x]);
    }
    for (int &y : vY[n]) {
        mY[y] = min(mY[y], d);
        ans[y] = min(ans[y], mX[y] + mY[y]);
    }
    for (auto &[m, w] : adj[n]) {
        if (!vis[m] && m != p) dfs(m, n, d + w);
    }
}

void revert(int n, int p) {
    for (int &x : vX[n]) mX[x] = 1e18;
    for (int &y : vY[n]) mY[y] = 1e18;
    for (auto &[m, w] : adj[n]) {
        if (!vis[m] && m != p) revert(m, n);
    }
}

void solve(int n) {
    int cap = getSz(n, -1);
    int cent = getCent(n, -1, cap);
    dfs(cent, -1, 0); revert(cent, -1);
    vis[cent] = 1;
    for (auto &[m, d] : adj[cent]) {
        if (!vis[m]) solve(m);
    }
}

int main() {
    cout.tie(0); cin.tie(0)->sync_with_stdio(0);
    memset(ans, 127, sizeof(ans));
    memset(vis, 0, sizeof(vis));
    memset(mX, 127, sizeof(mX));
    memset(mY, 127, sizeof(mY));

    cin >> N >> Q;
    for (int n = 0; n < N - 1; n++) {
        int A, B, D; cin >> A >> B >> D;
        adj[A].push_back({ B, D });
        adj[B].push_back({ A, D });
    }
    
    for (int q = 0; q < Q; q++) {
        int S, T; cin >> S >> T;
        for (int s = 0; s < S; s++) {
            int X; cin >> X;
            vX[X].push_back(q);
        }
        for (int t = 0; t < T; t++) {
            int Y; cin >> Y;
            vY[Y].push_back(q);
        }
    }

    solve(0);
    for (int q = 0; q < Q; q++) cout << ans[q] << '\n';
}

Compilation message (stderr)

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