oj.uz

Submission #883351

# Submission time Handle Problem Language Result Execution time Memory
883351 2023-12-05T08:01:14 Z vjudge1 Factories (JOI14_factories) C++17
100 / 100
 2692 ms 287728 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1'000'000'000'000'000'000;

const int N = 500'000;
const int M = 20;

int n, q, sz[N + 10], cnt[N + 10];
bool mark[N + 10];
ll mn[N + 10];
vector<pair<int, ll>> adj[N + 10];
pair<int, ll> up[N + 2][M + 2];
//int A[N + 10], B[N + 10], D[N + 10], X[N + 10], Y[N + 10], S, T;

int calcSz(int u, int par = 0) {
    sz[u] = 1;
    for (auto [v, w]: adj[u])
        if (!mark[v] && v != par)
            sz[u] += calcSz(v, u);
    return sz[u];
}

int calcCentroid(int u) {
    calcSz(u);
    int res = u;
    while (true) {
        int ok = res;
        for (auto [v, w]: adj[res])
            if (!mark[v] && sz[v] < sz[res] && sz[v] > sz[u] / 2)
                ok = v;
        if (ok == res)
            return res;
        res = ok;
    }
}

void calcH(int u, int root, int par = 0, ll h = 0) {
    up[u][cnt[u]++] = {root, h};
    for (auto [v, w]: adj[u])
        if (!mark[v] && v != par)
            calcH(v, root, u, h + w);
}

void makeGraph(int u = 1) {
    u = calcCentroid(u);
    calcH(u, u);
    mark[u] = true;
    for (auto [v, w]: adj[u])
        if (!mark[v])
            makeGraph(v);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++) {
        A[i]++;
        B[i]++;
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    makeGraph();
    fill(mn + 1, mn + n + 1, INF);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        X[i]++;
        for (int t = 0; t < cnt[X[i]]; t++)
            mn[up[X[i]][t].first] = min(mn[up[X[i]][t].first], up[X[i]][t].second);
    }
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        Y[i]++;
        for (int t = 0; t < cnt[Y[i]]; t++)
            ans = min(ans, mn[up[Y[i]][t].first] + up[Y[i]][t].second);
    }
    for (int i = 0; i < S; i++) 
        for (int t = 0; t < cnt[X[i]]; t++)
            mn[up[X[i]][t].first] = INF;
    return ans;
}

/*int main() {
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++)
        cin >> A[i] >> B[i] >> D[i];
    Init(n);
    vector<ll> vec;
    while (q--) {
        cin >> S >> T;
        for (int i = 0; i < S; i++)
            cin >> X[i];
        for (int i = 0; i < T; i++)
            cin >> Y[i];
        vec.push_back(Query());
    }
    for (auto x: vec)
        cout << x << ' ';
    cout.flush();
    return 0;
}*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35420 KB Output is correct
2 Correct 184 ms 41972 KB Output is correct
3 Correct 211 ms 41952 KB Output is correct
4 Correct 195 ms 41952 KB Output is correct
5 Correct 225 ms 42068 KB Output is correct
6 Correct 217 ms 46800 KB Output is correct
7 Correct 246 ms 46840 KB Output is correct
8 Correct 217 ms 46800 KB Output is correct
9 Correct 251 ms 47080 KB Output is correct
10 Correct 170 ms 46656 KB Output is correct
11 Correct 202 ms 46676 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 1272 ms 241444 KB Output is correct
3 Correct 1803 ms 245628 KB Output is correct
4 Correct 498 ms 257600 KB Output is correct
5 Correct 2374 ms 287728 KB Output is correct
6 Correct 1829 ms 264760 KB Output is correct
7 Correct 497 ms 95692 KB Output is correct
8 Correct 235 ms 94400 KB Output is correct
9 Correct 596 ms 98516 KB Output is correct
10 Correct 495 ms 95908 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 35420 KB Output is correct
2 Correct 184 ms 41972 KB Output is correct
3 Correct 211 ms 41952 KB Output is correct
4 Correct 195 ms 41952 KB Output is correct
5 Correct 225 ms 42068 KB Output is correct
6 Correct 217 ms 46800 KB Output is correct
7 Correct 246 ms 46840 KB Output is correct
8 Correct 217 ms 46800 KB Output is correct
9 Correct 251 ms 47080 KB Output is correct
10 Correct 170 ms 46656 KB Output is correct
11 Correct 202 ms 46676 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1272 ms 241444 KB Output is correct
14 Correct 1803 ms 245628 KB Output is correct
15 Correct 498 ms 257600 KB Output is correct
16 Correct 2374 ms 287728 KB Output is correct
17 Correct 1829 ms 264760 KB Output is correct
18 Correct 497 ms 95692 KB Output is correct
19 Correct 235 ms 94400 KB Output is correct
20 Correct 596 ms 98516 KB Output is correct
21 Correct 495 ms 95908 KB Output is correct
22 Correct 1293 ms 265092 KB Output is correct
23 Correct 1361 ms 266104 KB Output is correct
24 Correct 2122 ms 268528 KB Output is correct
25 Correct 2101 ms 268972 KB Output is correct
26 Correct 2074 ms 266724 KB Output is correct
27 Correct 2692 ms 286528 KB Output is correct
28 Correct 580 ms 262436 KB Output is correct
29 Correct 2085 ms 266520 KB Output is correct
30 Correct 2076 ms 267928 KB Output is correct
31 Correct 2093 ms 266576 KB Output is correct
32 Correct 645 ms 99152 KB Output is correct
33 Correct 246 ms 94400 KB Output is correct
34 Correct 408 ms 93636 KB Output is correct
35 Correct 422 ms 93524 KB Output is correct
36 Correct 499 ms 94412 KB Output is correct
37 Correct 478 ms 94292 KB Output is correct