Submission #1292552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292552		sonarcht	Factories (JOI14_factories)	C++20	15 / 100	821 ms	43812 KiB

factories

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

typedef long long ll;
typedef pair<ll,ll> pll; 
typedef vector<ll> vll;

const ll N = 100000 + 6, inf = (ll)1e18;
vector<pll> adj[N];
ll n, timer = 0;
ll tin[N], tout[N], d[N], up[N][21];
ll distv[N], mark[N];

vector<pll> aux[N];
priority_queue<pll, vector<pll>, greater<pll>> pq;

void dfs(ll p, ll u) {
    tin[u] = ++timer;
    for (auto [v,w] : adj[u]) {
        if (v == p) continue;
        d[v] = d[u] + w;
        up[v][0] = u;
        for (int j = 1; j <= 20; ++j) 
            up[v][j] = up[ up[v][j-1] ][j-1];
        dfs(u, v);
    }
    tout[u] = timer;
}

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

ll lca(ll u, ll v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int j = 20; j >= 0; --j)
        if (up[u][j] && !is_anc(up[u][j], v)) u = up[u][j];
    return up[u][0];
}

bool cmp(ll a, ll b) { return tin[a] < tin[b]; }

void dijkstra(vll& src) {
    while (!pq.empty()) pq.pop();
    for (ll s : src) {
        distv[s] = 0;
        pq.push({0, s});
    }
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du != distv[u]) continue;
        for (auto [v,w] : aux[u]) {
            if (du + w < distv[v]) {
                distv[v] = du + w;
                pq.push({distv[v], v});
            }
        }
    }
}

/* ===================== IOI MANDATED FUNCTIONS ===================== */

void Init(int Nn, int A[], int B[], int Dd[]) {
    n = Nn;

    for (int i = 1; i <= n; ++i) {
        adj[i].clear();
        for (int j = 0; j <= 20; ++j)
            up[i][j] = 0;
    }

    for (int i = 0; i < n-1; ++i) {
        int u = A[i] + 1;
        int v = B[i] + 1;
        int w = Dd[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    timer = 0;
    d[1] = 0;
    dfs(-1, 1);
}

long long Query(int S, int X[], int T, int Y[]) {
    vll v, v1, v2;
    for (int i = 0; i < S; ++i) {
        int x = X[i] + 1;
        v.push_back(x);
        v1.push_back(x);
        mark[x] = 1;
    }
    for (int i = 0; i < T; ++i) {
        int x = Y[i] + 1;
        v.push_back(x);
        v2.push_back(x);
        mark[x] = 2;
    }

    sort(v.begin(), v.end(), cmp);
    int sz = v.size();
    for (int i = 0; i < sz - 1; ++i)
        v.push_back(lca(v[i], v[i+1]));

    sort(v.begin(), v.end(), cmp);
    v.erase(unique(v.begin(), v.end()), v.end());

    stack<ll> st;
    for (ll u : v) {
        if (!st.empty() && !is_anc(st.top(), u))
            while (!st.empty() && !is_anc(st.top(), u)) st.pop();
        if (!st.empty()) {
            ll p = st.top();
            ll w = d[u] - d[p];
            aux[u].push_back({p, w});
            aux[p].push_back({u, w});
        }
        st.push(u);
    }

    for (ll x : v) distv[x] = inf;
    dijkstra(v1);

    ll ans = inf;
    for (ll u : v) if (mark[u] == 2) ans = min(ans, distv[u]);

    for (ll u : v) {
        aux[u].clear();
        mark[u] = 0;
        distv[u] = inf;
    }

    return ans;
}

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