Submission #1175792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175792		ahmedhali107	Factories (JOI14_factories)	C++20	Compilation error	0 ms	0 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const char nl = '\n', sp = ' ';

const ll inf = 1e18;

struct centroid_decomposition {
    int n;
    vector<vector<int> > anc;
    vector<vector<ll> > up;
    vector<vector<pair<int, int> > > g;
    vector<int> sz, colour;
    vector<map<ll, int> > closest;
    vector<bool> is_removed;

    centroid_decomposition() {
    }

    centroid_decomposition(int n) : n(n) {
        g.assign(n, {});
        anc.assign(n, {});
        closest.assign(n, {});
        up.assign(n, {});
        sz.assign(n, 0);
        colour.assign(n, 0);
        is_removed.assign(n, false);
    }

    void add_edge(int u, int v, int c) {
        g[u].emplace_back(v, c);
        g[v].emplace_back(u, c);
    }

    int get_size(int u, int p) {
        sz[u] = 1;
        for (auto &[v, _]: g[u]) {
            if (v == p || is_removed[v]) continue;
            sz[u] += get_size(v, u);
        }
        return sz[u];
    }

    int get_cent(int u, int p, int m) {
        for (auto &[v, _]: g[u]) {
            if (v == p || is_removed[v]) continue;
            if (sz[v] * 2 > m) return get_cent(v, u, m);
        }
        return u;
    }

    void add_node(int u, int p, int centroid, ll weight) {
        anc[u].push_back(centroid);
        up[u].push_back(weight);
        for (auto &[v, c]: g[u]) {
            if (v == p || is_removed[v]) continue;
            add_node(v, u, centroid, weight + c);
        }
    }

    void decompose(int u = 0) {
        int m = get_size(u, -1);
        int centroid = get_cent(u, -1, m);

        for (auto &[v, c]: g[centroid]) {
            if (is_removed[v]) continue;
            add_node(v, centroid, centroid, c);
        }

        is_removed[centroid] = 1;
        for (auto &[v, _]: g[centroid]) {
            if (is_removed[v]) continue;
            decompose(v);
        }
        reverse(all(anc[centroid]));
        reverse(all(up[centroid]));
    }

    void update(int u) {
        if (colour[u]) {
            remove(u);
        } else {
            add(u);
        }
        colour[u] ^= 1;
    }

    void add(int u) {
        closest[u][0]++;
        for (int i = 0; i < anc[u].size(); i++) {
            int p = anc[u][i], d = up[u][i];
            closest[p][d]++;
        }
    }

    void remove(int u) {
        if (--closest[u][0] == 0) closest[u].erase(0);
        for (int i = 0; i < anc[u].size(); i++) {
            int p = anc[u][i], d = up[u][i];
            if (--closest[p][d] == 0) closest[p].erase(d);
        }
    }

    ll query(int u) {
        ll ans = closest[u].empty() ? inf : closest[u].begin()->first;
        for (int i = 0; i < anc[u].size(); i++) {
            int p = anc[u][i], d = up[u][i];
            if (closest[p].size()) ans = min(ans, closest[p].begin()->first + d);
        }
        return ans == inf ? -1 : ans;
    }
};

centroid_decomposition cd;

void Init(int N, int A[], int B[], int D[]) {
    cd = N;
    for (int i = 0; i < N - 1; i++) {
        cd.add_edge(A[i], B[i], D[i]);
    }
    cd.decompose();
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        cd.update(X[i]);
    }
    ll ans = inf;
    for (int i = 0; i < T; i++) {
        ans = min(ans, cd.query(Y[i]));
    }
    for (int i = 0; i < S; i++) {
        cd.update(X[i]);
    }
    return ans;
}

void solve() {
    int n, q;
    cin >> n >> q;
    int a[n - 1], b[n - 1], d[n - 1];
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i] >> b[i] >> d[i];
    }
    Init(n, a, b, d);
    while (q--) {
        int s, t;
        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) << nl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

// #ifndef ONLINE_JUDGE
//     freopen("../in.txt", "r", stdin);
//     freopen("../out.txt", "w", stdout);
// #endif

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

Compilation message (stderr)

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