oj.uz

Submission #824457

# Submission time Handle Problem Language Result Execution time Memory
824457 2023-08-14T06:31:44 Z Koyote Factories (JOI14_factories) C++14
100 / 100
 3457 ms 362988 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 2;
const ll LINF = 1e18;

int n, subtree_size[MAXN];
vector<pair<int, ll>> adj[MAXN], ancestors[MAXN];
bitset<MAXN> removed;
ll min_dist_from_source[MAXN];

int dfs_subtree_size(int u, int p, ll depth, int anc) {
    subtree_size[u] = 1;
    if (anc != -1) ancestors[u].emplace_back(anc, depth);
    for (auto v : adj[u]) if (!removed[v.first] && v.first != p)
        subtree_size[u] += dfs_subtree_size(v.first, u, depth + v.second, anc);
    return subtree_size[u];
}

int find_centroid(int u, int p, int subt_sz) {
    for (auto v : adj[u]) if (!removed[v.first] && v.first != p && subtree_size[v.first] > subt_sz / 2)
        return find_centroid(v.first, u, subt_sz);
    return u;
}

void centroid_decompose(int u) {
    int c = find_centroid(u, -1, subtree_size[u]);
    removed[c] = 1;
    for (auto v : adj[c]) if (!removed[v.first])
        dfs_subtree_size(v.first, -1, v.second, c);
    for (auto v : adj[c]) if (!removed[v.first])
        centroid_decompose(v.first);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n; i++) min_dist_from_source[i] = LINF;
    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]);
    }

    dfs_subtree_size(0, -1, 0, -1);
    centroid_decompose(0);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll res = LINF;
    for (int i = 0; i < S; i++) {
        int u = X[i]; min_dist_from_source[u] = 0;
        for (auto v : ancestors[u])
            min_dist_from_source[v.first] = min(min_dist_from_source[v.first], v.second);
    }
    for (int i = 0; i < T; i++) {
        int u = Y[i];
        res = min(res, min_dist_from_source[u]);
        for (auto v : ancestors[u])
            res = min(res, min_dist_from_source[v.first] + v.second);
    }
    for (int i = 0; i < S; i++) {
        int u = X[i]; min_dist_from_source[u] = LINF;
        for (auto v : ancestors[u])
            min_dist_from_source[v.first] = LINF;
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24316 KB Output is correct
2 Correct 223 ms 42240 KB Output is correct
3 Correct 225 ms 42676 KB Output is correct
4 Correct 212 ms 42668 KB Output is correct
5 Correct 223 ms 43360 KB Output is correct
6 Correct 159 ms 41816 KB Output is correct
7 Correct 209 ms 42692 KB Output is correct
8 Correct 209 ms 42748 KB Output is correct
9 Correct 222 ms 43368 KB Output is correct
10 Correct 154 ms 41764 KB Output is correct
11 Correct 210 ms 42664 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24020 KB Output is correct
2 Correct 1738 ms 203828 KB Output is correct
3 Correct 2307 ms 251236 KB Output is correct
4 Correct 560 ms 99716 KB Output is correct
5 Correct 2958 ms 362988 KB Output is correct
6 Correct 2386 ms 252540 KB Output is correct
7 Correct 664 ms 82964 KB Output is correct
8 Correct 234 ms 58152 KB Output is correct
9 Correct 786 ms 89028 KB Output is correct
10 Correct 712 ms 84248 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24316 KB Output is correct
2 Correct 223 ms 42240 KB Output is correct
3 Correct 225 ms 42676 KB Output is correct
4 Correct 212 ms 42668 KB Output is correct
5 Correct 223 ms 43360 KB Output is correct
6 Correct 159 ms 41816 KB Output is correct
7 Correct 209 ms 42692 KB Output is correct
8 Correct 209 ms 42748 KB Output is correct
9 Correct 222 ms 43368 KB Output is correct
10 Correct 154 ms 41764 KB Output is correct
11 Correct 210 ms 42664 KB Output is correct
12 Correct 12 ms 24020 KB Output is correct
13 Correct 1738 ms 203828 KB Output is correct
14 Correct 2307 ms 251236 KB Output is correct
15 Correct 560 ms 99716 KB Output is correct
16 Correct 2958 ms 362988 KB Output is correct
17 Correct 2386 ms 252540 KB Output is correct
18 Correct 664 ms 82964 KB Output is correct
19 Correct 234 ms 58152 KB Output is correct
20 Correct 786 ms 89028 KB Output is correct
21 Correct 712 ms 84248 KB Output is correct
22 Correct 1968 ms 208052 KB Output is correct
23 Correct 2059 ms 214960 KB Output is correct
24 Correct 3174 ms 258136 KB Output is correct
25 Correct 3165 ms 262732 KB Output is correct
26 Correct 2805 ms 259564 KB Output is correct
27 Correct 3457 ms 362360 KB Output is correct
28 Correct 682 ms 110196 KB Output is correct
29 Correct 2812 ms 258696 KB Output is correct
30 Correct 2833 ms 257764 KB Output is correct
31 Correct 2804 ms 258684 KB Output is correct
32 Correct 841 ms 90272 KB Output is correct
33 Correct 248 ms 58620 KB Output is correct
34 Correct 501 ms 72080 KB Output is correct
35 Correct 501 ms 73084 KB Output is correct
36 Correct 712 ms 81136 KB Output is correct
37 Correct 719 ms 81196 KB Output is correct