Submission #1230986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230986		bb2009	Factories (JOI14_factories)	C++20	33 / 100	2315 ms	153560 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

const int MAXN = 5e5+5;
const long long INF = 1e18;

vector<pair<int, int>> adj[MAXN];
vector<pair<int, long long>> vt[MAXN];
int depth[MAXN], par[MAXN][20];
long long tin[MAXN], tout[MAXN], timer, dist[MAXN];
bool visited[MAXN], isY[MAXN];

void dfs(int u, int p) {
    par[u][0] = p;
    tin[u] = ++timer;
    for(int i = 1; i <= 17; i++) {
        par[u][i] = par[par[u][i-1]][i-1];
    }
    for(auto [v, w] : adj[u]) {
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        dist[v] = dist[u] + w;
        dfs(v, u);
    }
    tout[u] = timer;
}

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

int LCA(int u, int v) {
    if(isAncestor(u, v)) return u;
    if(isAncestor(v, u)) return v;
    for(int i = 17; i >= 0; i--) {
        if(!isAncestor(par[u][i], v)) u = par[u][i];
    }
    return par[u][0];
}

long long getDist(int u, int v) {
    int lca = LCA(u, v);
    return dist[u] + dist[v] - 2 * dist[lca];
}

void Init(int n, int A[], int B[], int D[]) {
    for(int i = 0; i < n - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> nodes;
    for(int i = 0; i < S; i++) {
        nodes.push_back(X[i]);
    }
    for(int i = 0; i < T; i++) {
        nodes.push_back(Y[i]);
        isY[Y[i]] = true;
    }

    sort(nodes.begin(), nodes.end(), [](int u, int v) { return tin[u] < tin[v]; });

    vector<int> allNodes = nodes;
    for(int i = 1; i < nodes.size(); i++) {
        allNodes.push_back(LCA(nodes[i - 1], nodes[i]));
    }

    sort(allNodes.begin(), allNodes.end(), [](int u, int v) { return tin[u] < tin[v]; });
    allNodes.erase(unique(allNodes.begin(), allNodes.end()), allNodes.end());

    stack<int> st;
    st.push(allNodes[0]);
    for(int i = 1; i < allNodes.size(); i++) {
        int u = allNodes[i];
        while(!isAncestor(st.top(), u)) st.pop();
        int v = st.top();
        long long d = getDist(u, v);
        vt[u].emplace_back(v, d);
        vt[v].emplace_back(u, d);
        st.push(u);
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;
    for(int i = 0; i < S; i++) {
        pq.emplace(0, X[i]);
    }

    long long res = INF;
    while(!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if(visited[u]) continue;
        visited[u] = true;
        if(isY[u]) {
            res = d;
            break;
        }
        for(auto [v, w] : vt[u]) {
            if(!visited[v]) pq.emplace(d + w, v);
        }
    }

    for(int u : allNodes) {
        vt[u].clear();
        visited[u] = false;
        isY[u] = false;
    }

    return res;
}

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