Submission #1230887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230887		wcarrotw	Factories (JOI14_factories)	C++17	33 / 100	8090 ms	154044 KiB

factories

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

#define fi first
#define se second
#define ll long long
#define bit(mask, i) ((mask >> i) & 1)
#define pb push_back

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

vector<pair<int, ll>> a[N], vtree[N];
int n, timer;
int tin[N], tout[N], tour[N], par[N], jump[N][LG], depth[N];
ll dist[N];
unordered_map<int, int> mp, color;
vector<int> type;
vector<ll> dp1, dp2;

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

void dfs1(int u, int p) {
    par[u] = p;
    tin[u] = ++timer;
    tour[timer] = u;
    for (auto &[v, w] : a[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dist[v] = dist[u] + w;
        dfs1(v, u);
    }
    tout[u] = timer;
}

void build_jump() {
    for (int i = 0; i < n; ++i) {
        jump[i][0] = par[i];
    }
    for (int j = 1; j < LG; ++j) {
        for (int i = 0; i < n; ++i) {
            if (jump[i][j - 1] != -1) {
                jump[i][j] = jump[jump[i][j - 1]][j - 1];
            }
        }
    }
}

int take(int u, int v) {
    int delta = depth[u] - depth[v];
    for (int i = 0; (1 << i) <= delta; ++i) {
        if (bit(delta, i)) {
            u = jump[u][i];
        }
    }
    return u;
}

int lca(int u, int v) {
    if (depth[u] != depth[v]) {
        if (depth[u] < depth[v]) swap(u, v);
        u = take(u, v);
    }
    if (u == v) return u;
    for (int i = LG - 1; i >= 0; --i) {
        if (jump[u][i] != jump[v][i]) {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    return jump[u][0];
}

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

ll get(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}

vector<int> buildtree(vector<int> tree) {
    sort(tree.begin(), tree.end(), cmp);
    int sz = tree.size();
    for (int i = 0; i < sz - 1; ++i) {
        tree.pb(lca(tree[i], tree[i + 1]));
    }
    sort(tree.begin(), tree.end());
    tree.erase(unique(tree.begin(), tree.end()), tree.end());
    sort(tree.begin(), tree.end(), cmp);
    stack<int> st;
    st.push(tree[0]);
    for (int i = 1; i < tree.size(); ++i) {
        while (!is_ancestor(st.top(), tree[i])) st.pop();
        vtree[st.top()].pb({tree[i], get(st.top(), tree[i])});
        st.push(tree[i]);
    }
    return tree;
}

int change(int x) {
    return mp[x];
}

void dfs2(int u, int p) {
    int _u = change(u);
    if (color[u] == 1) dp1[_u] = 0;
    if (color[u] == 2) dp2[_u] = 0;

    for (auto &[v, w] : vtree[u]) {
        if (v == p) continue;
        dfs2(v, u);
        int _v = change(v);
        dp1[_u] = min(dp1[_u], dp1[_v] + w);
        dp2[_u] = min(dp2[_u], dp2[_v] + w);
    }
}

// ============================
// Required functions for JOI:
// ============================

void Init(int N_, int A[], int B[], int D[]) {
    n = N_;
    for (int i = 0; i < n - 1; ++i) {
        int u = A[i], v = B[i]; ll w = D[i];
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    timer = 0;
    dfs1(0, -1);
    build_jump();
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> tree;
    for (int i = 0; i < S; ++i) {
        tree.pb(X[i]);
        color[X[i]] = 1;
    }
    for (int i = 0; i < T; ++i) {
        tree.pb(Y[i]);
        color[Y[i]] = 2;
    }

    tree = buildtree(tree);
    int root = tree[0], sz = tree.size();
    for (int i = 0; i < sz; ++i) {
        type.pb(color[tree[i]]);
        mp[tree[i]] = i;
    }

    dp1.assign(sz, inf), dp2.assign(sz, inf);
    dfs2(root, -1);

    ll res = inf;
    for (int i = 0; i < sz; ++i) {
        res = min(res, dp1[i] + dp2[i]);
    }

    // Clear memory
    for (int i = 0; i < sz; ++i) {
        vtree[tree[i]].clear();
    }
    color.clear(); mp.clear(); type.clear(); dp1.clear(); dp2.clear();

    return res;
}

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