Submission #1230993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230993		bb2009	Factories (JOI14_factories)	C++20	0 / 100	25 ms	24132 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;
long long dist[MAXN];
bool visited[MAXN];
long long dp[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 check(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (check(u, v)) return u;
    if (check(v, u)) return v;
    for (int i = 17; i >= 0; i--) {
        if (depth[u] - (1 << i) >= 0 && !check(par[u][i], v)) {
            u = par[u][i];
        }
    }
    return par[u][0];
}

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

void Init(int n, int A[], int B[], int D[]) {
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_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]);
        dp[Y[i]] = 0;
    }

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

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

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

    stack<int> st;
    st.push(all[0]);
    for (int i = 1; i < all.size(); i++) {
        int u = all[i];
        while (!check(st.top(), u)) st.pop();
        int v = st.top();
        long long d = get_dist(u, v);
        vt[u].push_back({v, d});
        vt[v].push_back({u, d});
        st.push(u);
    }

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    for (int i = 0; i < S; i++) {
        pq.push({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 (dp[u] == 0) {
            res = d;
            break;
        }
        for (auto [v, w] : vt[u]) {
            if (!visited[v]) pq.push({d + w, v});
        }
    }

    for (int u : all) {
        vt[u].clear();
        visited[u] = false;
        dp[u] = INF;
    }

    return res;
}

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