Submission #921975

#	Time	Username	Problem	Language	Result	Execution time	Memory
921975		406	Factories (JOI14_factories)	C++17	100 / 100	1800 ms	130644 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

using namespace std;
using ar = array<int, 2>;
const int64_t INF = 1ll << 60;
const int N = 5e5 + 5, LG = 19;

int n, T, st[N], fn[N], pr[N][LG];
long long h[N], dist[N];
vector<ar> adj[N];

bool is_anc(int v, int p) {
        return st[p] <= st[v] && fn[v] <= fn[p];
}

void dfs(int v, int p) {
        pr[v][0] = p;
        FOR(i, 0, LG - 1)
                pr[v][i + 1] = pr[pr[v][i]][i];
        st[v] = ++T;
        for (auto [u, w]: adj[v]) if (u != p) {
                h[u] = h[v] + w;
                dfs(u, v);
        }
        fn[v] = ++T;
}

int LCA(int u, int v) {
        if (is_anc(u, v)) return v;
        if (is_anc(v, u)) return u;
        for (int i = LG - 1; i >= 0; --i) if (!is_anc(u, pr[v][i]))
                v = pr[v][i];
        assert(!is_anc(u, v) && is_anc(u, pr[v][0]));
        return pr[v][0];
}

void Init(int NV, int A[], int B[], int D[]) {
        n = NV;
        FOR(i, 0, n - 1) {
                adj[A[i]].push_back({B[i], D[i]});
                adj[B[i]].push_back({A[i], D[i]});
        }
        dfs(0, 0);
        fill(dist, dist + N, INF);
}

int all[2 * N], cand[2 * N];

long long Query(int S, int X[], int T, int Y[]) {
        FOR(i, 0, S) dist[X[i]] = 0;

        copy(X, X + S, all);
        copy(Y, Y + T, all + S);

        int q = S + T, qq = q - 1;
        sort(all, all + q, [&](const int u, const int v) {return st[u] < st[v];});
        FOR(i, 0, q - 1) all[++qq] = LCA(all[i], all[i + 1]);

        q = qq + 1;
        sort(all, all + q, [&](const int u, const int v) {return fn[u] < fn[v];});
        int ptr = -1;
        FOR(i, 0, q) {
                int t = all[i], w;
                while (ptr >= 0 && is_anc(w = cand[ptr], t)) {
                        dist[t] = min(dist[t], dist[w] + h[w] - h[t]);
                        --ptr;
                }
                cand[++ptr] = all[i];
        }
        reverse(all, all + q);
        ptr = -1;
        FOR(i, 0, q) {
                int t = all[i], w;
                while (ptr >= 0 && !is_anc(t, w = cand[ptr]))
                        --ptr;
                if (ptr >= 0) 
                        dist[t] = min(dist[t], dist[w] + h[t] - h[w]);
                cand[++ptr] = all[i];
        }
        long long mn = dist[Y[0]];
        FOR(i, 1, T) mn = min(mn, dist[Y[i]]);
        FOR(i, 0, q) dist[all[i]] = INF;
        return mn;
}

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