Submission #1230896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230896		long290429	Factories (JOI14_factories)	C++20	0 / 100	1867 ms	111692 KiB

factories

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

const int MAXN = 500000 + 5;
int tin[MAXN], tout[MAXN], timer;
int dep[MAXN], dtr[MAXN];
vector<pair<int,int>> adj[MAXN];
int lg;
vector<vector<int>> up;

void dfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    for (int i = 1; i <= lg; ++i) {
        int mid = up[u][i-1];
        if (mid < 0) break;
        up[u][i] = up[mid][i-1];
    }
    for (auto &e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dtr[v] = dtr[u] + w;
        dfs(v, u);
    }
    tout[u] = timer;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int i = 0; diff; ++i) {
        if (diff & 1) u = up[u][i];
        diff >>= 1;
    }
    if (u == v) return u;
    for (int i = lg; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

long long solve(int a[], int n, int b[], int m) {
    // 1) collect nodes and add LCA of original neighbors
    vector<int> nodes;
    nodes.insert(nodes.end(), a, a + n);
    nodes.insert(nodes.end(), b, b + m);
    sort(nodes.begin(), nodes.end(), [&](int u, int v){ return tin[u] < tin[v]; });
    int orig = nodes.size();
    for (int i = 1; i < orig; ++i) {
        nodes.push_back(lca(nodes[i-1], nodes[i]));
    }
    sort(nodes.begin(), nodes.end(), [&](int u, int v){ return tin[u] < tin[v]; });
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
    int K = nodes.size();

    // 2) map and build virtual tree
    unordered_map<int,int> idx;
    idx.reserve(K);
    for (int i = 0; i < K; ++i) idx[nodes[i]] = i;

    vector<vector<pair<int,int>>> vt(K);
    vector<int> st;
    for (int u : nodes) {
        int uid = idx[u];
        while (!st.empty() && !(tin[nodes[st.back()]] <= tin[u] && tout[u] <= tout[nodes[st.back()]]))
            st.pop_back();
        if (!st.empty()) {
            int pid = st.back();
            int p = nodes[pid];
            int w = dtr[u] - dtr[p];
            vt[pid].emplace_back(uid, w);
            vt[uid].emplace_back(pid, w);
        }
        st.push_back(uid);
    }

    // 3) DP on virtual tree
    const long long INF = LLONG_MAX / 4;
    vector<long long> da(K, INF), db(K, INF);
    for (int i = 0; i < n; ++i) da[idx[a[i]]] = 0;
    for (int i = 0; i < m; ++i) db[idx[b[i]]] = 0;

    long long ans = INF;
    function<void(int,int)> dfs1 = [&](int u, int p) {
        for (auto &pr : vt[u]) {
            int v = pr.first, w = pr.second;
            if (v == p) continue;
            dfs1(v, u);
            da[u] = min(da[u], da[v] + w);
            db[u] = min(db[u], db[v] + w);
        }
        ans = min(ans, da[u] + db[u]);
    };
    dfs1(st[0], -1);

    function<void(int,int)> dfs2 = [&](int u, int p) {
        for (auto &pr : vt[u]) {
            int v = pr.first, w = pr.second;
            if (v == p) continue;
            da[v] = min(da[v], da[u] + w);
            db[v] = min(db[v], db[u] + w);
            ans = min(ans, da[v] + db[v]);
            dfs2(v, u);
        }
    };
    dfs2(st[0], -1);

    return ans;
}

void Init(int n, int U[], int V[], int W[]) {
    for (int i = 0; i < n; ++i) adj[i].clear();
    for (int i = 0; i < n-1; ++i) {
        adj[U[i]].emplace_back(V[i], W[i]);
        adj[V[i]].emplace_back(U[i], W[i]);
    }
    timer = 0;
    fill(dep, dep+n, 0);
    fill(dtr, dtr+n, 0);
    lg = floor(log2(max(1, n)));
    up.assign(n, vector<int>(lg+1, -1));
    dfs(0, -1);
}

long long Query(int s, int A[], int t, int B[]) {
    return solve(A, s, B, t);
}

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