Submission #1175801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175801		ahmedhali107	Factories (JOI14_factories)	C++20	100 / 100	2683 ms	270096 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<ll> closest;
    vector<bool> is_removed;

    centroid_decomposition() {
    }

    centroid_decomposition(int n) : n(n) {
        g.assign(n, {});
        anc.assign(n, {});
        closest.assign(n, inf);
        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];
            ll d = up[u][i];
            closest[p] = min(closest[p], d);
        }
    }

    void remove(int u) {
        closest[u] = inf;
        for (int i = 0; i < anc[u].size(); i++) {
            int p = anc[u][i];
            closest[p] = inf;
        }
    }

    ll query(int u) {
        ll ans = closest[u];
        for (int i = 0; i < anc[u].size(); i++) {
            int p = anc[u][i];
            ll d = up[u][i];
            ans = min(ans, closest[p] + d);
        }
        return 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;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67