제출 #1134207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134207		Nelt	공장들 (JOI14_factories)	C++20	100 / 100	5136 ms	413644 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], d[N];
pair<ll, ll> st[lg][N << 1];
vector<ll> order;
bool used[N];
void dfs(ll v, ll par = 0)
{
    order.push_back(v);
    d[v] = order.size() - 1;
    for (auto [to, w] : g[v])
        if (to != par)
        {
            depth[to] = depth[v] + 1, dis[to] = dis[v] + w, dfs(to, v);
            order.push_back(v);
        }
}
void build()
{
    for (ll i = 0; i < order.size(); i++) st[0][i] = make_pair(depth[order[i]], order[i]);
    for (ll i = 1; i < lg; i++)
    for (ll j = 0; j + (1 << i) - 1 < order.size(); j++) st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
ll lca(ll a, ll b)
{
    a = d[a];
    b = d[b];
    if (a > b) swap(a, b);
    ll lg = __lg(b - a + 1);
    return min(st[lg][a], st[lg][b - (1 << lg) + 1]).second;
}
ll dist(ll a, ll b)
{
    return dis[a] + dis[b] - dis[lca(a, b)] * 2;
}
ll getcentroid(ll v, ll mx, ll par = -1)
{
    for (auto [to, w] : g[v])
        if (to != par and !used[to] and sub[to] > (mx >> 1))
            return getcentroid(to, mx, v);
    return v;
}
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)
{
    init(v);
    return getcentroid(v, sub[v], -1);
}
ll decompose(ll v)
{
    ll cent = findcentroid(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);
    for (ll i = 0; i < n; i++) best[i] = 1e18, p[i] = -1;
    decompose(0);
    build();
}

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

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