oj.uz

Submission #730591

# Submission time Handle Problem Language Result Execution time Memory
730591 2023-04-26T06:56:02 Z t6twotwo Factories (JOI14_factories) C++17
100 / 100
 6040 ms 225668 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> p, dep, euler, P, lg;
vector<int64_t> dis, best;
vector<vector<int>> st;
vector<vector<pair<int, int>>> adj;
constexpr int64_t inf = 1E18;
int F(int x, int y) {
    return dep[x] < dep[y] ? x : y;
}
int lca(int x, int y) {
    if (x == y) {
        return x;
    }
    if (P[x] > P[y]) {
        swap(x, y);
    }
    int z = lg[P[y] - P[x] + 1];
    return F(st[P[x]][z], st[P[y] + 1 - (1 << z)][z]);
}
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    p.resize(N);
    P.resize(N);
    dis.resize(N);
    dep.resize(N);
    adj.resize(N);
    best.resize(N, inf);
    lg.resize(2 * N + 1);
    for (int i = 2; i <= 2 * N; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    st = vector(2 * N - 1, vector<int>(lg[2 * N - 1] + 1, -1));
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    auto dfs = [&](auto dfs, int x, int p) -> void {
        P[x] = euler.size();
        euler.push_back(x);
        for (auto [y, z] : adj[x]) {
            if (y == p) {
                continue;
            }
            dep[y] = dep[x] + 1;
            dis[y] = dis[x] + z;
            dfs(dfs, y, x);
            euler.push_back(x);
        }
    };
    dfs(dfs, 0, -1);
    for (int i = 0; i < 2 * N - 1; i++) {
        st[i][0] = euler[i];
    }
    for (int j = 0; j < lg[2 * N - 1]; j++) {
        for (int i = 0; i + (2 << j) < 2 * N; i++) {
            st[i][j + 1] = F(st[i][j], st[i + (1 << j)][j]);
        }
    }
    vector<bool> vis(N);
    vector<int> sz(N);
    auto init = [&](auto init, int x, int p) -> void {
        sz[x] = 1;
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y]) {
                continue;
            }
            init(init, y, x);
            sz[x] += sz[y];
        }
    };
    auto find = [&](auto find, int x, int p, int s) -> int {
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y] || sz[y] * 2 <= s) {
                continue;
            }
            return find(find, y, x, s);
        }
        return x;
    };
    auto cd = [&](auto cd, int x) -> int {
        init(init, x, -1);
        x = find(find, x, -1, sz[x]);
        vis[x] = 1;
        for (auto [y, _] : adj[x]) {
            if (vis[y]) {
                continue;
            }
            p[cd(cd, y)] = x;
        }
        return x;
    };
    p[cd(cd, 0)] = -1;
}
int64_t dist(int x, int y) {
    return dis[x] + dis[y] - 2 * dis[lca(x, y)];
}
long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        int x = X[i];
        while (x != -1) {
            best[x] = min(best[x], dist(x, X[i]));
            x = p[x];
        }
    }
    auto ans = inf;
    for (int i = 0; i < T; i++) {
        int x = Y[i];
        while (x != -1) {
            ans = min(ans, best[x] + dist(x, Y[i]));
            x = p[x];
        }
    }
    for (int i = 0; i < S; i++) {
        int x = X[i];
        while (x != -1) {
            best[x] = inf;
            x = p[x];
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 648 KB Output is correct
2 Correct 387 ms 9748 KB Output is correct
3 Correct 455 ms 9980 KB Output is correct
4 Correct 507 ms 9760 KB Output is correct
5 Correct 490 ms 10008 KB Output is correct
6 Correct 196 ms 9764 KB Output is correct
7 Correct 439 ms 9768 KB Output is correct
8 Correct 427 ms 9800 KB Output is correct
9 Correct 568 ms 10008 KB Output is correct
10 Correct 187 ms 9800 KB Output is correct
11 Correct 418 ms 9816 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2406 ms 184484 KB Output is correct
3 Correct 3516 ms 185012 KB Output is correct
4 Correct 939 ms 199544 KB Output is correct
5 Correct 4301 ms 219884 KB Output is correct
6 Correct 3337 ms 205252 KB Output is correct
7 Correct 1944 ms 56088 KB Output is correct
8 Correct 494 ms 56976 KB Output is correct
9 Correct 1946 ms 59080 KB Output is correct
10 Correct 1827 ms 57424 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 648 KB Output is correct
2 Correct 387 ms 9748 KB Output is correct
3 Correct 455 ms 9980 KB Output is correct
4 Correct 507 ms 9760 KB Output is correct
5 Correct 490 ms 10008 KB Output is correct
6 Correct 196 ms 9764 KB Output is correct
7 Correct 439 ms 9768 KB Output is correct
8 Correct 427 ms 9800 KB Output is correct
9 Correct 568 ms 10008 KB Output is correct
10 Correct 187 ms 9800 KB Output is correct
11 Correct 418 ms 9816 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 2406 ms 184484 KB Output is correct
14 Correct 3516 ms 185012 KB Output is correct
15 Correct 939 ms 199544 KB Output is correct
16 Correct 4301 ms 219884 KB Output is correct
17 Correct 3337 ms 205252 KB Output is correct
18 Correct 1944 ms 56088 KB Output is correct
19 Correct 494 ms 56976 KB Output is correct
20 Correct 1946 ms 59080 KB Output is correct
21 Correct 1827 ms 57424 KB Output is correct
22 Correct 3550 ms 210288 KB Output is correct
23 Correct 3496 ms 213120 KB Output is correct
24 Correct 4909 ms 211616 KB Output is correct
25 Correct 5047 ms 215208 KB Output is correct
26 Correct 5294 ms 211540 KB Output is correct
27 Correct 6040 ms 225668 KB Output is correct
28 Correct 1219 ms 213784 KB Output is correct
29 Correct 4883 ms 211392 KB Output is correct
30 Correct 4866 ms 210864 KB Output is correct
31 Correct 4743 ms 211332 KB Output is correct
32 Correct 2009 ms 59740 KB Output is correct
33 Correct 453 ms 57408 KB Output is correct
34 Correct 1520 ms 54076 KB Output is correct
35 Correct 1516 ms 54152 KB Output is correct
36 Correct 1694 ms 54464 KB Output is correct
37 Correct 1835 ms 54408 KB Output is correct