oj.uz

Submission #921972

# Submission time Handle Problem Language Result Execution time Memory
921972 2024-02-04T15:29:11 Z 406 Factories (JOI14_factories) C++17
100 / 100
 2096 ms 150412 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];

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];});
        vector<int> cand;
        FOR(i, 0, q) {
                int t = all[i], w;
                while (cand.size() && is_anc(w = cand.back(), t)) {
                        dist[t] = min(dist[t], dist[w] + h[w] - h[t]);
                        cand.pop_back();
                }
                cand.push_back(all[i]);
        }
        cand.clear();
        sort(all, all + q, [&](const int u, const int v) {return st[u] < st[v];}); //reverse fn doroste aya?
        FOR(i, 0, q) {
                int t = all[i], w;
                while (cand.size() && !is_anc(t, w = cand.back()))
                        cand.pop_back();
                if (cand.size())
                        dist[t] = min(dist[t], dist[w] + h[t] - h[w]);
                cand.push_back(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 23 ms 42588 KB Output is correct
2 Correct 906 ms 56192 KB Output is correct
3 Correct 768 ms 56208 KB Output is correct
4 Correct 807 ms 56224 KB Output is correct
5 Correct 492 ms 56484 KB Output is correct
6 Correct 565 ms 56144 KB Output is correct
7 Correct 755 ms 56144 KB Output is correct
8 Correct 737 ms 56140 KB Output is correct
9 Correct 514 ms 56484 KB Output is correct
10 Correct 570 ms 56236 KB Output is correct
11 Correct 781 ms 56204 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 42332 KB Output is correct
2 Correct 968 ms 123472 KB Output is correct
3 Correct 1136 ms 125388 KB Output is correct
4 Correct 711 ms 123948 KB Output is correct
5 Correct 738 ms 147580 KB Output is correct
6 Correct 1227 ms 126284 KB Output is correct
7 Correct 945 ms 71888 KB Output is correct
8 Correct 538 ms 72060 KB Output is correct
9 Correct 430 ms 74856 KB Output is correct
10 Correct 929 ms 72784 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42588 KB Output is correct
2 Correct 906 ms 56192 KB Output is correct
3 Correct 768 ms 56208 KB Output is correct
4 Correct 807 ms 56224 KB Output is correct
5 Correct 492 ms 56484 KB Output is correct
6 Correct 565 ms 56144 KB Output is correct
7 Correct 755 ms 56144 KB Output is correct
8 Correct 737 ms 56140 KB Output is correct
9 Correct 514 ms 56484 KB Output is correct
10 Correct 570 ms 56236 KB Output is correct
11 Correct 781 ms 56204 KB Output is correct
12 Correct 9 ms 42332 KB Output is correct
13 Correct 968 ms 123472 KB Output is correct
14 Correct 1136 ms 125388 KB Output is correct
15 Correct 711 ms 123948 KB Output is correct
16 Correct 738 ms 147580 KB Output is correct
17 Correct 1227 ms 126284 KB Output is correct
18 Correct 945 ms 71888 KB Output is correct
19 Correct 538 ms 72060 KB Output is correct
20 Correct 430 ms 74856 KB Output is correct
21 Correct 929 ms 72784 KB Output is correct
22 Correct 2080 ms 130388 KB Output is correct
23 Correct 1807 ms 131632 KB Output is correct
24 Correct 2096 ms 132612 KB Output is correct
25 Correct 2008 ms 134856 KB Output is correct
26 Correct 1999 ms 130640 KB Output is correct
27 Correct 1272 ms 150412 KB Output is correct
28 Correct 1174 ms 133284 KB Output is correct
29 Correct 1962 ms 130252 KB Output is correct
30 Correct 1867 ms 129920 KB Output is correct
31 Correct 1973 ms 130592 KB Output is correct
32 Correct 779 ms 78240 KB Output is correct
33 Correct 783 ms 75176 KB Output is correct
34 Correct 1133 ms 70728 KB Output is correct
35 Correct 1114 ms 70720 KB Output is correct
36 Correct 1060 ms 71220 KB Output is correct
37 Correct 1059 ms 71192 KB Output is correct