oj.uz

Submission #1108974

# Submission time Handle Problem Language Result Execution time Memory
1108974 2024-11-05T18:15:12 Z doducanh Factories (JOI14_factories) C++14
100 / 100
 3652 ms 362776 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std; 
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 5e5 + 2;
const ll INF = 1e14 + 2;

vector<ll> dist(N);
vector<int> sz(N), is_dead(N, 0);
vector<vector<pair<int, ll>>> edges(N), cent(N);

int n;
void find_sz(int node, int parent) {
    sz[node] = 1;
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        find_sz(child.first, node);
        sz[node] += sz[child.first];
    }
}

void update(int node, int parent, int c, ll d) {
    cent[node].push_back(make_pair(c, d));
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        update(child.first, node, c, d + child.second);
    }
}

void find_cent(int node, int parent, int size) {
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        if (sz[child.first] * 2 > size) {
            find_cent(child.first, node, size);
            return;
        }
    }
    update(node, -1, node, 0);
    is_dead[node] = 1;
    find_sz(node, -1);
    for (auto child :edges[node]) {
        if (is_dead[child.first]) continue;
        find_cent(child.first, node, sz[child.first]);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; i++) {
        edges[A[i]].push_back(make_pair(B[i], D[i]));
        edges[B[i]].push_back(make_pair(A[i], D[i]));
    }
    find_sz(0, -1);
    find_cent(0, -1, N);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        for (auto p : cent[Y[i]]) {
            dist[p.first] = INF;
        }
    }
    for (int i = 0; i < S; i++) {
        for (auto p : cent[X[i]]) {
            dist[p.first] = min(dist[p.first], p.second);
        }
    }
    for (int i = 0; i < T; i++) {
        for (auto p : cent[Y[i]]) {
            ans = min(ans, dist[p.first] + p.second);
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 48208 KB Output is correct
2 Correct 199 ms 53348 KB Output is correct
3 Correct 228 ms 61252 KB Output is correct
4 Correct 230 ms 61204 KB Output is correct
5 Correct 241 ms 58912 KB Output is correct
6 Correct 169 ms 52808 KB Output is correct
7 Correct 215 ms 58684 KB Output is correct
8 Correct 223 ms 58696 KB Output is correct
9 Correct 232 ms 61520 KB Output is correct
10 Correct 155 ms 57672 KB Output is correct
11 Correct 207 ms 61208 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 48208 KB Output is correct
2 Correct 1609 ms 222132 KB Output is correct
3 Correct 2426 ms 293344 KB Output is correct
4 Correct 527 ms 116348 KB Output is correct
5 Correct 2985 ms 362776 KB Output is correct
6 Correct 2541 ms 295068 KB Output is correct
7 Correct 532 ms 98952 KB Output is correct
8 Correct 244 ms 75704 KB Output is correct
9 Correct 659 ms 106824 KB Output is correct
10 Correct 519 ms 94116 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 48208 KB Output is correct
2 Correct 199 ms 53348 KB Output is correct
3 Correct 228 ms 61252 KB Output is correct
4 Correct 230 ms 61204 KB Output is correct
5 Correct 241 ms 58912 KB Output is correct
6 Correct 169 ms 52808 KB Output is correct
7 Correct 215 ms 58684 KB Output is correct
8 Correct 223 ms 58696 KB Output is correct
9 Correct 232 ms 61520 KB Output is correct
10 Correct 155 ms 57672 KB Output is correct
11 Correct 207 ms 61208 KB Output is correct
12 Correct 13 ms 48208 KB Output is correct
13 Correct 1609 ms 222132 KB Output is correct
14 Correct 2426 ms 293344 KB Output is correct
15 Correct 527 ms 116348 KB Output is correct
16 Correct 2985 ms 362776 KB Output is correct
17 Correct 2541 ms 295068 KB Output is correct
18 Correct 532 ms 98952 KB Output is correct
19 Correct 244 ms 75704 KB Output is correct
20 Correct 659 ms 106824 KB Output is correct
21 Correct 519 ms 94116 KB Output is correct
22 Correct 1709 ms 216996 KB Output is correct
23 Correct 1917 ms 220664 KB Output is correct
24 Correct 2939 ms 285888 KB Output is correct
25 Correct 2949 ms 301616 KB Output is correct
26 Correct 2866 ms 278668 KB Output is correct
27 Correct 3652 ms 346680 KB Output is correct
28 Correct 744 ms 112808 KB Output is correct
29 Correct 2683 ms 277844 KB Output is correct
30 Correct 2606 ms 278080 KB Output is correct
31 Correct 2948 ms 296432 KB Output is correct
32 Correct 790 ms 106864 KB Output is correct
33 Correct 272 ms 70328 KB Output is correct
34 Correct 465 ms 88036 KB Output is correct
35 Correct 459 ms 90952 KB Output is correct
36 Correct 560 ms 98632 KB Output is correct
37 Correct 548 ms 92528 KB Output is correct