제출 #1234381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234381		musanna47	공장들 (JOI14_factories)	C++20	100 / 100	6570 ms	255420 KiB

factories

// Author: Muhtasim Hossain Musanna (Musanna47 / mhmusanna)

#include "factories.h"
#include "bits/stdc++.h"

using namespace std;


#define nl "\n"
#define REPF(_i, _a, _b) for(int _i = _a; _i <= _b; _i++)
#define REPB(_i, _a, _b) for(int _i = _a; _i >= _b; _i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
#define sza(_x) ((int)_x.size())
#define all(_x) _x.begin(), _x.end()
#define sort_des(_x) sort(all(_x), greater())
#define min_heap(_T, _pq, _cmp) auto _cmp = greater(); priority_queue<_T, vector<_T>, decltype(_cmp)> _pq(_cmp)


template<typename T1, typename T2>
using P = pair<T1, T2>;
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using VVV = V<V<V<T>>>;
template<typename T>
using VVVV = V<V<V<V<T>>>>;


using S = string;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pii = P<int, int>;
using pll = P<ll, ll>;
using vi = V<int>;
using vvi = VV<int>;
using vll = V<ll>;
using vvll = VV<ll>;
using vpii = V<pii>;
using vpll = V<pll>;


template<typename T>
void pout(T &a, string sep = " ", string fin = "\n") {
    cout << a.first << sep << a.second << fin;
}

template<typename T>
void print(T &a, ll l, ll r, string sep = " ", string fin = "\n") {
    for (ll i = l; i <= r; i++)
        cout << a[i] << sep;
    cout << fin;
}

template<typename T>
void printPairs(T &a, ll l, ll r, string fin = "\n") {
    for (ll i = l; i <= r; i++)
        pout(a[i]);
    cout << fin;
}

template<typename T>
void printAll(T &a, string sep = " ", string fin = "\n") {
    for (auto &ele: a)
        cout << ele << sep;
    cout << fin;
}

template<typename T>
void printPairsAll(T &a, string fin = "\n") {
    for (auto &ele: a)
        pout(ele);
    cout << fin;
}

template<typename... Args>
void read(Args &... args) {
    ((cin >> args), ...);
}

template<typename... Args>
void out(Args... args) {
    ((cout << args << " "), ...);
}

template<typename... Args>
void outln(Args... args) {
    ((cout << args << " "), ...);
    cout << nl;
}

template<typename T>
void vin(T &a, ll l, ll r) {
    for (ll i = l; i <= r; i++)
        cin >> a[i];
}


using bll = __int128;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LL_INF = 1e18;
const double PI = 3.141592653589793;
const double EPS = 1e-12;


const int MAXN = 5e5 + 5;
const int H = 20;
vpii G[MAXN];
int subsize[MAXN];
bitset<MAXN> done;
multiset<ll> dists[MAXN];
int ancNode[MAXN][H + 1];
ll ancDist[MAXN][H + 1];


void getSubSize(int node, int par) {
    subsize[node] = 1;
    for (auto &[child, w]: G[node]) {
        if (child != par && !done[child]) {
            getSubSize(child, node);
            subsize[node] += subsize[child];
        }
    }
}

void calc(int node, int par, int centroid, int h, ll dist) {
    ancNode[node][h] = centroid;
    ancDist[node][h] = dist;
    for (auto &[child, w]: G[node]) {
        if (child != par && !done[child]) {
            calc(child, node, centroid, h, dist + w);
        }
    }
}

void centroidDecomp(int node = 1, int h = 0) {
    // Get subtree sizes
    getSubSize(node, -1);

    // Get centroid
    int centroid = node, par = -1;
    while (true) {
        bool stop = true;
        for (auto &[child, w]: G[centroid]) {
            if (child != par && !done[child]) {
                if (subsize[child] > subsize[node] / 2) {
                    stop = false;
                    par = centroid, centroid = child;
                    break;
                }
            }
        }
        if (stop)
            break;
    }

    // Mark centroid as done
    done[centroid] = true;

    // Perform task / query
    calc(centroid, centroid, centroid, h, 0);

    // Find next centroid
    for (auto &[child, w]: G[centroid]) {
        if (!done[child])
            centroidDecomp(child, h + 1);
    }
}

void update(int node, bool f) {
    for (int h = 0; h <= H && ancNode[node][h]; h++) {
        auto &par = ancNode[node][h];
        auto &dist = ancDist[node][h];
        if (f)
            dists[par].emplace(dist);
        else
            dists[par].extract(dist);
    }
}

ll query(int node) {
    ll ret = LL_INF;
    for (int h = 0; h <= H && ancNode[node][h]; h++) {
        auto &par = ancNode[node][h];
        auto &dist = ancDist[node][h];
        if (!dists[par].empty())
            ret = min(ret, dist + *dists[par].begin());
    }
    return ret;
}


void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        G[A[i] + 1].emplace_back(B[i] + 1, D[i]);
        G[B[i] + 1].emplace_back(A[i] + 1, D[i]);
    }
    centroidDecomp();
}


long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++)
        update(X[i] + 1, true);
    ll ans = LL_INF;
    for (int i = 0; i < T; i++)
        ans = min(ans, query(Y[i] + 1));
    for (int i = 0; i < S; i++)
        update(X[i] + 1, false);
    return ans;
}

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