제출 #1134081

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134081		Nelt	공장들 (JOI14_factories)	C++20	0 / 100	1697 ms	21668 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less_equal<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 5e5 + 5, lg = 20;
vector<pair<ll, ll>> g[N];
ll sub[N], p[N], n, up[lg][N], depth[N], dis[N], best[N];
bool used[N];
void dfs(ll v, ll par = -1)
{
    up[0][v] = par;
    for (ll i = 1; i < lg; i++) up[i][v] = up[i - 1][up[i - 1][v]];
    for (auto [to, w] : g[v])
        if (to != par) depth[to] = depth[v] + 1, dis[to] = dis[v] + w, dfs(to, v);
}
ll lca(ll a, ll b)
{
    if (depth[a] < depth[b]) swap(a, b);
    for (ll bit = lg - 1; bit >= 0; bit--) if (depth[a] - (1 << bit) >= depth[b]) a = up[bit][a];
    if (a == b) return a;
    for (ll bit = lg - 1; bit >= 0; bit--) if (up[bit][a] != up[bit][b]) a = up[bit][a], b = up[bit][b];
    return up[0][a];
}
ll dist(ll a, ll b)
{
    return dis[a] + dis[b] - dis[lca(a, b)] * 2;
}
void init(ll v, ll par = -1)
{
    sub[v] = 1;
    for (auto [to, w] : g[v])
        if (to != par and !used[to]) init(to, v), sub[v] += sub[to];
}
ll findcentroid(ll v, ll par = -1, ll sz = 0)
{
    for (auto [to, w] : g[v])
        if (to != par and !used[to] and sub[to] > sz / 2) return findcentroid(to, v, sz); 
    return v;
}
ll decompose(ll v)
{
    init(v);
    ll cent = findcentroid(v, -1, sub[v]);
    used[cent] = 1;
    for (auto [to, w] : g[cent])
        if (!used[to])
            p[decompose(to)] = cent;
    return cent;
}
void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for (ll i = 0; i < n - 1; i++) g[A[i]].push_back(make_pair(B[i], D[i])), g[B[i]].push_back(make_pair(A[i], D[i]));
    dfs(0);
    decompose(0);
    for (ll i = 0; i < n; i++) best[i] = 1e18;
}

long long Query(int S, int X[], int T, int Y[])
{
    for (ll i = 0; i < S; i++)
    {
        ll v = X[i];
        while (true)
        {
            best[v] = min(best[v], dist(v, X[i]));
            if (v == 0) break;
            v = p[v];
        }
    }
    ll ans = 9e18;
    for (ll i = 0; i < T; i++)
    {
        ll v = Y[i];
        while (true)
        {
            ans = min(ans, best[v] + dist(v, Y[i]));
            if (v == 0) break;
            v = p[v];
        }
    }
    for (ll i = 0; i < S; i++)
    {
        ll v = X[i];
        while (true)
        {
            best[v] = 1e18;
            if (v == 0) break;
            v = p[v];
        }
    }
    return ans;
}

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