Submission #1175796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175796		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)
#define int long long
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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccVvQQwU.o: in function `main':
grader.cpp:(.text.startup+0x3d5): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x468): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status