oj.uz

답안 #1031045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031045 2024-07-22T13:51:38 Z PVSekhar 공장들 (JOI14_factories) C++14
100 / 100
 3301 ms 367892 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

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32088 KB Output is correct
2 Correct 184 ms 40716 KB Output is correct
3 Correct 202 ms 41300 KB Output is correct
4 Correct 208 ms 41320 KB Output is correct
5 Correct 236 ms 51028 KB Output is correct
6 Correct 148 ms 49748 KB Output is correct
7 Correct 210 ms 50600 KB Output is correct
8 Correct 217 ms 50772 KB Output is correct
9 Correct 257 ms 51028 KB Output is correct
10 Correct 147 ms 49744 KB Output is correct
11 Correct 202 ms 50788 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 31836 KB Output is correct
2 Correct 1584 ms 197192 KB Output is correct
3 Correct 2410 ms 285708 KB Output is correct
4 Correct 559 ms 110004 KB Output is correct
5 Correct 3000 ms 361496 KB Output is correct
6 Correct 2501 ms 287196 KB Output is correct
7 Correct 530 ms 89356 KB Output is correct
8 Correct 229 ms 66496 KB Output is correct
9 Correct 630 ms 103652 KB Output is correct
10 Correct 553 ms 91008 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 32088 KB Output is correct
2 Correct 184 ms 40716 KB Output is correct
3 Correct 202 ms 41300 KB Output is correct
4 Correct 208 ms 41320 KB Output is correct
5 Correct 236 ms 51028 KB Output is correct
6 Correct 148 ms 49748 KB Output is correct
7 Correct 210 ms 50600 KB Output is correct
8 Correct 217 ms 50772 KB Output is correct
9 Correct 257 ms 51028 KB Output is correct
10 Correct 147 ms 49744 KB Output is correct
11 Correct 202 ms 50788 KB Output is correct
12 Correct 14 ms 31836 KB Output is correct
13 Correct 1584 ms 197192 KB Output is correct
14 Correct 2410 ms 285708 KB Output is correct
15 Correct 559 ms 110004 KB Output is correct
16 Correct 3000 ms 361496 KB Output is correct
17 Correct 2501 ms 287196 KB Output is correct
18 Correct 530 ms 89356 KB Output is correct
19 Correct 229 ms 66496 KB Output is correct
20 Correct 630 ms 103652 KB Output is correct
21 Correct 553 ms 91008 KB Output is correct
22 Correct 1929 ms 221144 KB Output is correct
23 Correct 1827 ms 226100 KB Output is correct
24 Correct 2941 ms 293472 KB Output is correct
25 Correct 2915 ms 297748 KB Output is correct
26 Correct 2663 ms 294460 KB Output is correct
27 Correct 3301 ms 367892 KB Output is correct
28 Correct 670 ms 119984 KB Output is correct
29 Correct 2651 ms 293712 KB Output is correct
30 Correct 2835 ms 293892 KB Output is correct
31 Correct 2664 ms 293692 KB Output is correct
32 Correct 632 ms 104024 KB Output is correct
33 Correct 209 ms 67012 KB Output is correct
34 Correct 360 ms 81744 KB Output is correct
35 Correct 411 ms 82516 KB Output is correct
36 Correct 554 ms 87640 KB Output is correct
37 Correct 537 ms 87724 KB Output is correct