oj.uz

Submission #921975

# Submission time Handle Problem Language Result Execution time Memory
921975 2024-02-04T15:34:14 Z 406 Factories (JOI14_factories) C++17
100 / 100
 1800 ms 130644 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44124 KB Output is correct
2 Correct 643 ms 48616 KB Output is correct
3 Correct 598 ms 48612 KB Output is correct
4 Correct 591 ms 48608 KB Output is correct
5 Correct 428 ms 48980 KB Output is correct
6 Correct 505 ms 48624 KB Output is correct
7 Correct 609 ms 48608 KB Output is correct
8 Correct 591 ms 48868 KB Output is correct
9 Correct 425 ms 48720 KB Output is correct
10 Correct 505 ms 48612 KB Output is correct
11 Correct 606 ms 48720 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 44124 KB Output is correct
2 Correct 911 ms 106424 KB Output is correct
3 Correct 1117 ms 109488 KB Output is correct
4 Correct 663 ms 107380 KB Output is correct
5 Correct 669 ms 130644 KB Output is correct
6 Correct 1205 ms 109628 KB Output is correct
7 Correct 882 ms 60244 KB Output is correct
8 Correct 561 ms 60096 KB Output is correct
9 Correct 370 ms 62688 KB Output is correct
10 Correct 843 ms 60644 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44124 KB Output is correct
2 Correct 643 ms 48616 KB Output is correct
3 Correct 598 ms 48612 KB Output is correct
4 Correct 591 ms 48608 KB Output is correct
5 Correct 428 ms 48980 KB Output is correct
6 Correct 505 ms 48624 KB Output is correct
7 Correct 609 ms 48608 KB Output is correct
8 Correct 591 ms 48868 KB Output is correct
9 Correct 425 ms 48720 KB Output is correct
10 Correct 505 ms 48612 KB Output is correct
11 Correct 606 ms 48720 KB Output is correct
12 Correct 8 ms 44124 KB Output is correct
13 Correct 911 ms 106424 KB Output is correct
14 Correct 1117 ms 109488 KB Output is correct
15 Correct 663 ms 107380 KB Output is correct
16 Correct 669 ms 130644 KB Output is correct
17 Correct 1205 ms 109628 KB Output is correct
18 Correct 882 ms 60244 KB Output is correct
19 Correct 561 ms 60096 KB Output is correct
20 Correct 370 ms 62688 KB Output is correct
21 Correct 843 ms 60644 KB Output is correct
22 Correct 1631 ms 107720 KB Output is correct
23 Correct 1451 ms 108884 KB Output is correct
24 Correct 1566 ms 110004 KB Output is correct
25 Correct 1552 ms 111868 KB Output is correct
26 Correct 1700 ms 108276 KB Output is correct
27 Correct 1153 ms 129256 KB Output is correct
28 Correct 1102 ms 111568 KB Output is correct
29 Correct 1708 ms 107908 KB Output is correct
30 Correct 1671 ms 107368 KB Output is correct
31 Correct 1800 ms 107940 KB Output is correct
32 Correct 619 ms 67668 KB Output is correct
33 Correct 687 ms 64344 KB Output is correct
34 Correct 839 ms 59036 KB Output is correct
35 Correct 827 ms 59044 KB Output is correct
36 Correct 920 ms 59516 KB Output is correct
37 Correct 876 ms 59728 KB Output is correct