Submission #1267762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267762		bbldrizzy	Factories (JOI14_factories)	C++20	0 / 100	1028 ms	121220 KiB

factories

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

using P = pair<int, int>;
#define f first
#define s second
const int INF = 1e9;

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

// --- Centroid decomposition utilities ---

int sz(int nd, int 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];
}

int cen(int nd, int pr, int 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(int nd, int pr, int cent, int 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(int nd) {
    int 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(int nd) {
    for (auto x: unc[nd]) {
        mn[x.f] = min(mn[x.f], x.s);
    }
    mn[nd] = 0;
}

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

int qry(int nd) {
    int 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++) {
        int a = A[i];
        int b = B[i];
        int 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]);
    }

    int 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: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67