Submission #1280770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280770		chanhchuong123	Factories (JOI14_factories)	C++20	100 / 100	3990 ms	331592 KiB

factories

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

const bool multiTest = false;
#define task "C"
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)

template<typename T1, typename T2> bool minimize(T1 &a, T2 b) {
	if (a > b) a = b; else return 0; return 1;
}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b) {
	if (a < b) a = b; else return 0; return 1;
}

const long long oo = 1e18 + 7;
const int MAX = 500050;
int N, Q;
int sz[MAX];
bool rem[MAX];
long long minDist[MAX];
vector<pair<int, int>> adj[MAX];
vector<pair<int, long long>> ancestors[MAX];

int dfsSZ(int u, int p) {
    sz[u] = 1;
    for (auto &[v, w]: adj[u]) if (v != p && !rem[v]) {
        sz[u] += dfsSZ(v, u);
    }
    return sz[u];
}

int findCentroid(int u, int p, int n) {
    for (auto &[v, w]: adj[u]) if (v != p && !rem[v]) {
        if (2 * sz[v] > n)
            return findCentroid(v, u, n);
    }
    return u;
}

void decomposition(int u, int p) {
    int c = findCentroid(u, p, dfsSZ(u, p)); rem[c] = 1; 

    queue<tuple<int, int, long long>> q;
    q.emplace(c, p, 0);
    while (q.size()) {
        auto [u, p, dist] = q.front(); q.pop();
        ancestors[u].emplace_back(c, dist);
        for (auto &[_u, _w]: adj[u]) if (_u != p && !rem[_u]) {
            q.emplace(_u, u, dist + _w);
        }
    }

    for (auto &[v, w]: adj[c]) if (v != c && !rem[v]) {
        decomposition(v, c);
    }
}

void Init(int _N, int _A[], int _B[], int _D[]) {
    N = _N;
    for (int i = 0; i < N - 1; ++i) {
        adj[_A[i]].emplace_back(_B[i], _D[i]);
        adj[_B[i]].emplace_back(_A[i], _D[i]);
    }
    decomposition(0, -1);
    for (int i = 0; i < N; ++i) {
        minDist[i] = oo;
        rem[i] = 0;
    }
}

void update(int v, int t) {
    for (auto &[c, dist]: ancestors[v]) {
        long long &dp = minDist[c];
        if (!t) dp = oo; else minimize(dp, dist);
    }
}

long long get(int v) {
    long long res = oo; for (auto &[c, dist]: ancestors[v]) minimize(res, dist + minDist[c]);
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < T; ++i) {
        update(Y[i], 1);
    }
    long long res = oo;
    for (int i = 0; i < S; ++i) {
        minimize(res, get(X[i]));
    }
    for (int i = 0; i < T; ++i) {
        update(Y[i], 0);
    }
    return res;
}

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