Submission #1054062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054062		manhlinh1501	Factories (JOI14_factories)	C++17	100 / 100	1620 ms	181888 KiB

factories

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using i64 = long long;
const int MAXN = 5e5 + 5;
const int LOGN = 20;
const i64 oo64 = 1e18;
#define ALL(a) (a).begin(), (a).end()
int N, Q;
vector<pii> adj[MAXN];
int up[MAXN][LOGN];
int depth[MAXN];
int tin[MAXN];
int tout[MAXN];
int tdfs = 0;
i64 dist[MAXN];
i64 dp[MAXN][2];
vector<int> g[MAXN];

void DFS(int u, int p) {
    depth[u] = depth[p] + 1;
    tin[u] = ++tdfs;
    up[u][0] = p;
    for(int i = 1; i < LOGN; i++) up[u][i] = up[up[u][i - 1]][i - 1];

    for(auto [v, w] : adj[u]) {
        if(v == p) continue;
        dist[v] = dist[u] + w;
        DFS(v, u);
    }
    tout[u] = tdfs;
}

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

int LCA(int u, int v) {
    if(depth[u] != depth[v]) {
        if(depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        for(int i = 0; (1 << i) <= k; i++) {
            if(k >> i & 1)
                u = up[u][i];
        }
    }
    if(u == v) return u;
    int k = 31 - __builtin_clz(depth[u]);
    for(int i = k; i >= 0; i--) {
        if(up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

i64 get_dist(int u, int v) {
    return dist[u] + dist[v] - 2 * dist[LCA(u, v)];
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N - 1; i++) {
        int u = A[i];
        int v = B[i];
        int w = D[i];
        u++;
        v++;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for(int i = 1; i <= N; i++) dp[i][0] = dp[i][1] = oo64;
    DFS(1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> ver;
    for(int i = 0; i < S; i++) {
        int u = X[i];
        u++;
        dp[u][0] = dist[u];
        ver.emplace_back(u);
    }
    for(int i = 0; i < T; i++) {
        int u = Y[i];
        u++;
        dp[u][1] = dist[u];
        ver.emplace_back(u);
    }
    sort(ALL(ver), [&](const int a, const int b) {
        return tin[a] < tin[b];
    });
    ver.resize(unique(ALL(ver)) - ver.begin());
    int M = ver.size();
    for(int i = 0; i < M; i++)
        ver.emplace_back(LCA(ver[i], ver[i + 1]));
    sort(ALL(ver), [&](const int a, const int b) {
        return tin[a] < tin[b];
    });
    ver.resize(unique(ALL(ver)) - ver.begin());
    stack<int> st;
    for(int x : ver) {
        while(!st.empty() and inside(st.top(), x) == false)
            st.pop();
        if(!st.empty()) {
            int u = st.top();
            g[u].emplace_back(x);
        }
        st.emplace(x);
    }
    reverse(ALL(ver));
    for(int x : ver) {
        for(int v : g[x]) {
            for(int j = 0; j < 2; j++)
                dp[x][j] = min(dp[x][j], dp[v][j]);
        }
    }
    i64 ans = oo64;
    for(int x : ver) {
        ans = min(ans, dp[x][0] + dp[x][1] - 2 * dist[x]);
    }

    for(int x : ver) {
        g[x].clear();
        dp[x][0] = dp[x][1] = oo64;
    }
    return ans;
}

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