제출 #1195074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195074		og_matveychick1	Factories (JOI14_factories)	C++20	100 / 100	4209 ms	205548 KiB

factories

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

using namespace std;

typedef long long ll;
typedef vector<ll> vll;


const ll N = 5e5 + 5, K = 20;

ll n, in[N], ou[N], ti, up[K][N], d[N], u1[N], u2[N], dp[N][2];
vector<pair<ll, ll>> g[N], g1[N];

bool cmp(ll x, ll y) {
    return in[x] < in[y];
}

bool is_p(ll u, ll v) {
    return in[u] <= in[v] && ou[u] >= ou[v];
}

ll lca(ll u, ll v) {
    if (u == v) return u;
    if (in[u] > in[v]) swap(u, v);
    for (ll i = K - 1; i >= 0; i--) if (!is_p(up[i][v], u)) v = up[i][v];
    return up[0][v];
}

void dfs(ll v, ll p) {
    in[v] = ti++;
    up[0][v] = p;
    for (ll i = 1; i < K; i++) up[i][v] = up[i - 1][up[i - 1][v]];
    for (auto [x, w]: g[v]) {
        if (x == p) continue;
        d[x] = d[v] + w;
        dfs(x, v);
    }
    ou[v] = ti;
}

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({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
}

void build(vll s) {
    vll st;
    for (auto x: s) {
        while (st.size() && !is_p(st.back(), x)) st.pop_back();
        if (st.size()) g1[st.back()].push_back({x, d[x] - d[st.back()]});
        st.push_back(x);
    }
}

void go(ll v) {
    dp[v][0] = dp[v][1] = 1e18;
    if (u1[v]) dp[v][0] = 0;
    if (u2[v]) dp[v][1] = 0;
    for (auto [x, w]: g1[v]) {
        go(x);
        dp[v][0] = min(dp[v][0], dp[x][0] + w);
        dp[v][1] = min(dp[v][1], dp[x][1] + w);
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<ll> s;
    for (ll i = 0; i < S; i++) s.push_back(X[i]);
    for (ll i = 0; i < T; i++) s.push_back(Y[i]);
    sort(s.begin(), s.end(), cmp);
    for (ll i = 0; i < S + T - 1; i++) s.push_back(lca(s[i], s[i + 1]));
    sort(s.begin(), s.end(), cmp);
    s.resize(unique(s.begin(), s.end()) - s.begin());
    build(s);
    for (auto x: s) u1[x] = u2[x] = 0;
    for (ll i = 0; i < S; i++) u1[X[i]] = 1;
    for (ll i = 0; i < T; i++) u2[Y[i]] = 1;
    go(s[0]);
    ll ans = 1e18;
    for (auto x: s) ans = min(ans, dp[x][0] + dp[x][1]);
    for (auto x: s) g1[x].clear();
    return ans;
}

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