Submission #1267764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267764		bbldrizzy	Factories (JOI14_factories)	C++20	100 / 100	2856 ms	326108 KiB

factories

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

using ll = long long;
using P = pair<ll, ll>;
#define f first
#define s second
const ll INF = 4e18;

static vector<vector<pair<ll,ll>>> adj; // adjacency list <neighbor, cost>
static vector<ll> st;
static vector<ll> mn;
static vector<bool> rem;
static vector<vector<pair<ll,ll>>> unc; // unc[v] = list of (centroid, dist)

// --- Centroid decomposition utilities ---

ll sz(ll nd, ll pr = -1) {
    st[nd] = 1;
    for (auto c: adj[nd]) {
        if (c.f == pr || rem[c.f]) continue;
        st[nd] += sz(c.f, nd);
    }
    return st[nd];
}

ll cen(ll nd, ll pr, ll tot) {
    for (auto c: adj[nd]) {
        if (c.f == pr || rem[c.f]) continue;
        if (st[c.f]*2 > tot) return cen(c.f, nd, tot);
    }
    return nd;
}

void calc_dist(ll nd, ll pr, ll cent, ll cdist) {
    for (auto c: adj[nd]) {
        if (c.f == pr || rem[c.f]) continue;
        cdist += c.s;
        calc_dist(c.f, nd, cent, cdist);
        cdist -= c.s;
    }
    unc[nd].push_back({cent, cdist});
}

void build(ll nd) {
    ll cent = cen(nd, -1, sz(nd));
    for (auto c: adj[cent]) {
        if (rem[c.f]) continue;
        calc_dist(c.f, cent, cent, c.s);
    }
    rem[cent] = true;
    for (auto c: adj[cent]) {
        if (!rem[c.f]) build(c.f);
    }
}

// --- Paint / Query helpers ---

void paint(ll nd) {
    for (auto x: unc[nd]) {
        mn[x.f] = min(mn[x.f], x.s);
    }
    mn[nd] = 0;
}

void unpaint(ll nd) {
    for (auto x: unc[nd]) {
        mn[x.f] = INF;
    }
    mn[nd] = INF;
}

ll qry(ll nd) {
    ll ans = mn[nd];
    for (auto x: unc[nd]) {
        ans = min(ans, mn[x.f] + x.s);
    }
    return ans;
}

// --- Required interface ---

void Init(int N, int A[], int B[], int D[]) {
    adj.assign(N, {});
    for (int i = 0; i < N-1; i++) {
        ll a = A[i];
        ll b = B[i];
        ll c = D[i];
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    st.assign(N, 0);
    rem.assign(N, false);
    unc.assign(N, {});
    build(0);
    mn.assign(N, INF);
}

long long Query(int S, int X[], int T, int Y[]) {
    // Paint all nodes in Y
    for (int i = 0; i < T; i++) {
        paint(Y[i]);
    }

    ll ans = INF;
    for (int i = 0; i < S; i++) {
        ans = min(ans, qry(X[i]));
    }

    // Unpaint nodes in Y
    for (int i = 0; i < T; i++) {
        unpaint(Y[i]);
    }

    return ans;
}

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