Submission #1230967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230967		vkchudeanhlo	Factories (JOI14_factories)	C++20	100 / 100	3200 ms	159680 KiB

factories

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

const int max_n = 500005;
const int log_n = 20;
const long long inf = 1e18;

vector<pair<int, int>> adj[max_n];
vector<pair<long long, long long>> tree[max_n];

int up[max_n][log_n];
int depth[max_n];
long long dist[max_n];
long long tin[max_n], tout[max_n], timer = 0;
long long dp[max_n];
bool visited[max_n];

void dfs(int u, int parent) {
    up[u][0] = parent;
    for (int i = 1; i < log_n; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    tin[u] = ++timer;
    for (int i = 0; i < (int)adj[u].size(); i++) {
        int to = adj[u][i].first;
        int w = adj[u][i].second;
        if (to != parent) {
            depth[to] = depth[u] + 1;
            dist[to] = dist[u] + w;
            dfs(to, u);
        }
    }
    tout[u] = timer;
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) {
        int temp = u;
        u = v;
        v = temp;
    }
    for (int i = log_n - 1; i >= 0; i--) {
        if (up[u][i] != -1 && depth[up[u][i]] >= depth[v]) {
            u = up[u][i];
        }
    }
    if (u == v) return u;
    for (int i = log_n - 1; i >= 0; i--) {
        if (up[u][i] != -1 && 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 cmp(int a, int b) {
    return tin[a] < tin[b];
}

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]].push_back(make_pair(b[i], d[i]));
        adj[b[i]].push_back(make_pair(a[i], d[i]));
    }
    for (int i = 0; i < log_n; i++) up[0][i] = 0;
    depth[0] = 0;
    dist[0] = 0;
    dfs(0, 0);
    for (int i = 0; i < n; i++) dp[i] = -1;
}

long long Query(int s, int x[], int t, int y[]) {
    vector<int> spec;
    for (int i = 0; i < s; i++) spec.push_back(x[i]);
    for (int i = 0; i < t; i++) {
        spec.push_back(y[i]);
        dp[y[i]] = 0;
    }

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

    stack<int> st;
    st.push(nodes[0]);
    for (int i = 1; i < (int)nodes.size(); i++) {
        int u = nodes[i];
        while (!is_ancestor(st.top(), u)) st.pop();
        int v = st.top();
        long long d = get_dist(u, v);
        tree[u].push_back(make_pair(v, d));
        tree[v].push_back(make_pair(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(make_pair(0, x[i]));
    }

    long long res = inf;
    while (!pq.empty()) {
        pair<long long, int> top = pq.top(); pq.pop();
        long long d = top.first;
        int u = top.second;
        if (dp[u] == 0) {
            res = d;
            break;
        }
        if (visited[u]) continue;
        visited[u] = true;
        for (int i = 0; i < (int)tree[u].size(); i++) {
            int to = tree[u][i].first;
            long long w = tree[u][i].second;
            pq.push(make_pair(d + w, to));
        }
    }

    for (int i = 0; i < (int)nodes.size(); i++) {
        int u = nodes[i];
        tree[u].clear();
        visited[u] = false;
        dp[u] = -1;
    }

    return res;
}

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