Submission #1230959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230959		vkchudeanhlo	Factories (JOI14_factories)	C++20	100 / 100	3596 ms	159748 KiB

factories

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

const int MAXN = 500005;
const int LOG = 20;
const long long INF = 1e18;

vector<pair<int, int>> adj[MAXN];
vector<pair<long long, long long>> vtree[MAXN];

int up[MAXN][LOG];
int depth[MAXN];
long long dist[MAXN];
long long tin[MAXN], tout[MAXN], timer;
long long dp[MAXN];
bool vis[MAXN];

void dfs(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < LOG; ++i)
        up[u][i] = up[up[u][i - 1]][i - 1];
    tin[u] = ++timer;
    for (auto &e : adj[u]) {
        int v = e.first, w = e.second;
        if (v != p) {
            depth[v] = depth[u] + 1;
            dist[v] = dist[u] + w;
            dfs(v, u);
        }
    }
    tout[u] = timer;
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; --i)
        if (depth[up[u][i]] >= depth[v])
            u = up[u][i];
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i)
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

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

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

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]);
    }
    depth[0] = dist[0] = 0;
    timer = 0;
    dfs(0, 0);
    fill(dp, dp + n, -1);
}

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 a, int b) { return tin[a] < tin[b]; });

    vector<int> unique_nodes = nodes;
    for (int i = 1; i < (int)nodes.size(); ++i)
        unique_nodes.push_back(lca(nodes[i - 1], nodes[i]));
    sort(unique_nodes.begin(), unique_nodes.end(), [](int a, int b) { return tin[a] < tin[b]; });
    unique_nodes.erase(unique(unique_nodes.begin(), unique_nodes.end()), unique_nodes.end());

    stack<int> stk;
    stk.push(unique_nodes[0]);
    for (int i = 1; i < (int)unique_nodes.size(); ++i) {
        int u = unique_nodes[i];
        while (!is_ancestor(stk.top(), u)) stk.pop();
        int p = stk.top();
        long long d = get_dist(u, p);
        vtree[u].emplace_back(p, d);
        vtree[p].emplace_back(u, d);
        stk.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 (dp[u] == 0) {
            res = d;
            break;
        }
        if (vis[u]) continue;
        vis[u] = true;
        for (auto &[v, w] : vtree[u]) pq.emplace(d + w, v);
    }

    for (int u : unique_nodes) {
        vtree[u].clear();
        vis[u] = false;
        dp[u] = -1;
    }

    return res;
}

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