Submission #1230996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230996		bb2009	Factories (JOI14_factories)	C++20	100 / 100	3421 ms	160868 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define ii pair<ll,ll>
#define fi first
#define se second
#define all(a) a.begin(),a.end()

using namespace std;

const int N = 5e5 + 5;
const ll inf = 1e18;
const int LOG = 20;

vector<pair<int, int>> adj[N];
vector<ii> v[N];  // virtual tree
int up[N][LOG];
int depth[N];
ll dist[N];
ll tin[N], tout[N], timer = 0;
ll dp[N];
bool visited[N];

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 [to, w] : adj[u]) {
        if (to != p) {
            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]) swap(u, v);
    for (int i = LOG - 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 - 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];
}

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

bool sort_tin(const ll &a, const ll &b) {
    return tin[a] < tin[b];
}

bool is_ancestor(ll u, ll 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]].pb({B[i], D[i]});
        adj[B[i]].pb({A[i], D[i]});
    }
    for (int i = 0; i < LOG; i++) up[0][i] = 0;
    depth[0] = 0;
    dist[0] = 0;
    dfs(0, 0);
    memset(dp,-1,sizeof(dp));
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<ll> special;
    for (int i = 0; i < S; i++) special.pb(X[i]);
    for (int i = 0; i < T; i++) {
        special.pb(Y[i]);
        dp[Y[i]] = 0;
    }

    sort(all(special), sort_tin);
    vector<ll> node = special;

    for (int i = 1; i < special.size(); i++) {
        node.pb(lca(special[i - 1], special[i]));
    }
    sort(all(node), sort_tin);
    node.erase(unique(all(node)), node.end());

    stack<ll> st;
    st.push(node[0]);
    for (int i = 1; i < node.size(); i++) {
        ll u = node[i];
        while (!is_ancestor(st.top(), u)) st.pop();
        ll x = st.top();
        ll d = get_dist(u, x);
        v[u].pb({x, d});
        v[x].pb({u, d});
        st.push(u);
    }
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    for (int i = 0; i < S; i++) pq.push({0, X[i]});
    ll ans = inf;
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
       // cout<<d<<" "<<u<<'\n';
        if (dp[u] == 0) {
            ans = d;
            break;
        }
        if (visited[u]) continue;
        visited[u] = true;
        for (auto [to, w] : v[u]) {
            pq.push({d + w, to});
        }
    }

    for (auto u : node) {
        v[u].clear();
        visited[u] = 0;
        dp[u] = -1;
    }

    return ans;
}

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