Submission #1230970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230970		long290429	Factories (JOI14_factories)	C++20	100 / 100	2279 ms	153288 KiB

factories

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

const int MAXN = 500000;
int N, Q;

// cây ban đầu
vector<pair<int,long long>> adj[MAXN];
int tin[MAXN], tout[MAXN], dep[MAXN];
long long dtr[MAXN];
int tt, lg;
vector<vector<int>> up;

// DFS build LCA, tính tin/tout và dtr[]
void dfs(int u, int p) {
    tin[u] = ++tt;
    up[u][0] = p;
    for(int i = 1; i <= lg; i++) {
        int pi = up[u][i-1];
        up[u][i] = (pi < 0 ? -1 : up[pi][i-1]);
    }
    for(auto &e : adj[u]) {
        int v = e.first;
        long long w = e.second;
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        dtr[v] = dtr[u] + w;
        dfs(v, u);
    }
    tout[u] = tt;
}

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++, diff >>= 1)
        if (diff & 1) u = up[u][i];
    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];
}

const long long INF = (long long)4e18;

// solve cho 1 query: tập A cỡ n, tập B cỡ m
long long solve(int A[], int n, int B[], int m) {
    // 1) gom chung
    vector<int> vs;
    vs.reserve(n + m);
    for(int i = 0; i < n; i++) vs.push_back(A[i]);
    for(int i = 0; i < m; i++) vs.push_back(B[i]);

    // 2) sort theo tin rồi thêm LCA của cặp liền kề
    sort(vs.begin(), vs.end(), [&](int x,int y){ return tin[x] < tin[y]; });
    int K = vs.size();
    for(int i = 1; i < K; i++)
        vs.push_back(lca(vs[i-1], vs[i]));

    // 3) unique + sort lại
    sort(vs.begin(), vs.end(), [&](int x,int y){ return tin[x] < tin[y]; });
    vs.erase(unique(vs.begin(), vs.end()), vs.end());
    int sz = vs.size();

    // 4) đánh chỉ số
    unordered_map<int,int> idx;
    idx.reserve(sz*1.3);
    for(int i = 0; i < sz; i++) idx[vs[i]] = i;

    // 5) build virtual-tree
    vector<vector<pair<int,long long>>> vt(sz);
    vector<int> st;
    st.reserve(sz);
    for(int i = 0; i < sz; i++){
        int u = vs[i], idu = i;
        while(!st.empty()) {
            int top = st.back();
            int v = vs[top];
            if (tin[v] <= tin[u] && tout[u] <= tout[v]) break;
            st.pop_back();
        }
        if (!st.empty()) {
            int top = st.back();
            int v = vs[top];
            long long w = dtr[u] - dtr[v];
            vt[top].emplace_back(idu, w);
            vt[idu].emplace_back(top, w);
        }
        st.push_back(idu);
    }

    // 6) multi-source init
    vector<long long> da(sz, INF), db(sz, 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;
    // post-order
    function<void(int,int)> dfs1 = [&](int u, int p){
        for(auto &e: vt[u]) {
            int v = e.first;
            long long w = e.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]);
    };
    // pre-order
    function<void(int,int)> dfs2 = [&](int u, int p){
        for(auto &e: vt[u]) {
            int v = e.first;
            long long w = e.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);
        }
    };

    int root = st.front();
    dfs1(root, -1);
    dfs2(root, -1);

    return ans;
}

// được gọi 1 lần
void Init(int N, int U[], int V[], int D[]) {
    ::N = N;
    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], (long long)D[i]);
        adj[V[i]].emplace_back(U[i], (long long)D[i]);
    }
    tt = 0;
    dep[0] = dtr[0] = 0;
    lg = floor(log2(N));
    up.assign(N, vector<int>(lg+1, -1));
    dfs(0, -1);
}

// được gọi Q lần
long long Query(int S, int X[], int T, int Y[]) {
    return solve(X, S, Y, T);
}

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