Submission #1293236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293236		thaibeo123	Factories (JOI14_factories)	C++20	100 / 100	1736 ms	215404 KiB

factories

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

#define NAME "A"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define MASK(x) (1ll << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

const int N = 5e5 + 5;
const int LG = 20;
const ll inf = 1e18;

int n, timer, tour;
int tin[N], tout[N], yes[N], hi[N];
int ri[N], st[N * 2][21];
ll val[N], dp[N][2];
vector<int> vec;
vector<pair<int, ll>> adj[N], g[N];

bool cmp(int u, int v) {
    return tin[u] < tin[v];
}

bool inside(int u, int v) {
    return tin[u] <= tin[v] && tin[v] <= tout[u];
}

int lca(int u, int v) {
    int l = ri[u], r = ri[v];
    if (l > r) swap(l, r);
    int k = __lg(r - l + 1);
    u = st[l][k];
    v = st[r - MASK(k) + 1][k];
    return (hi[u] < hi[v] ? u : v);
}

void init(int u, int par) {
    tin[u] = ++timer;
    st[++tour][0] = u;
    ri[u] = tour;
    hi[u] = hi[par] + 1;
    for (auto it : adj[u]) {
        int v = it.fi, w = it.se;
        if (v == par) continue;
        val[v] = val[u] + w;
        init(v, u);
        st[++tour][0] = u;
    }
    tout[u] = timer;
}

void dfs(int u, int par) {
    for (auto it : g[u]) {
        int v = it.fi;
        ll w = it.se;
        if (v == par) continue;
        dfs(v, u);
        dp[u][0] = min(dp[u][0], dp[v][0] + w);
    }
    if (yes[u] == 2) {
        dp[u][0] = 0;
    }
}

void reroot(int u, int par) {
    ll mn = dp[u][1];
    if (yes[u] == 2) mn = 0;
    for (int i = g[u].size() - 1; i >= 0; i--) {
        int v = g[u][i].fi;
        ll w = g[u][i].se;
        if (v == par) continue;
        dp[v][1] = min(dp[v][1], mn + w);
        mn = min(mn, dp[v][0] + w);
    }
    mn = inf;
    for (auto it : g[u]) {
        int v = it.fi;
        ll w = it.se;
        if (v == par) continue;
        dp[v][1] = min(dp[v][1], mn + w);
        reroot(v, u);
        mn = min(mn, dp[v][0] + w);
    }
}

void build_virtual_tree() {
    sort(all(vec), cmp);
    vec.erase(unique(all(vec)), vec.end());
    int cur = vec.size();
    for (int i = 1; i < cur; i++) {
        vec.pb(lca(vec[i - 1], vec[i]));
    }
    sort(all(vec), cmp);
    vec.erase(unique(all(vec)), vec.end());
    stack<int> st;
    st.push(vec[0]);
    for (int i = 1; i < (int)vec.size(); i++) {
        while (!inside(st.top(), vec[i])) {
            st.pop();
        }
        int u = st.top();
        int v = vec[i];
        g[u].pb({v, val[v] - val[u]});
        g[v].pb({u, val[v] - val[u]});
        st.push(vec[i]);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i <= n - 2; i++) {
        int u = A[i], v = B[i], d = D[i];
        u++, v++;
        adj[u].pb({v, d});
        adj[v].pb({u, d});
    }
    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i][1] = inf;
    }
    init(1, 0);
    for (int j = 1; j <= LG; j++) {
        for (int i = 1; i + MASK(j) - 1 <= tour; i++) {
            int u = st[i][j - 1];
            int v = st[i + MASK(j - 1)][j - 1];
            st[i][j] = (hi[u] < hi[v] ? u : v);
        }
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        X[i]++;
        yes[X[i]] = 1;
        vec.pb(X[i]);
    }
    for (int i = 0; i < T; i++) {
        Y[i]++;
        yes[Y[i]] = 2;
        vec.pb(Y[i]);
    }
    build_virtual_tree();
    dfs(vec[0], 0);
    reroot(vec[0], 0);
    ll ans = inf;
    for (int x : vec) {
        if (yes[x] == 1) {
            ans = min({ans, dp[x][0], dp[x][1]});
        }
        yes[x] = 0;
        dp[x][0] = dp[x][1] = inf;
        g[x].clear();
    }
    vec.clear();
    return ans;
}

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