oj.uz

Submission #1084143

# Submission time Handle Problem Language Result Execution time Memory
1084143 2024-09-05T10:59:50 Z f0rizen Factories (JOI14_factories) C++17
100 / 100
 3067 ms 213720 KB 
#include "factories.h"

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

struct Edge {
    int to, w;
};

vector<vector<Edge>> g;
vector<bool> used;
vector<int> sz, par;
vector<vector<ll>> dist;
vector<ll> closest;

void dfs_sz(int v, int p = -1) {
    sz[v] = 1;
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            dfs_sz(u, v);
            sz[v] += sz[u];
        }
    }
}

void dfs_dist(int v, int p = -1, ll d = 0) {
    dist[v].push_back(d);
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            dfs_dist(u, v, d + w);
        }
    }
}

int centroid(int v, int p, int n) {
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            if (sz[u] * 2 > n) {
                return centroid(u, v, n);
            }
        }
    }
    return v;
}

void build(int v, int p = -1) {
    dfs_sz(v);
    dfs_dist(v);
    par[v] = p;
    used[v] = 1;
    for (auto [u, w] : g[v]) {
        if (!used[u]) {
            build(centroid(u, v, sz[u]), v);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    g.resize(N);
    for (int i = 0; i < N - 1; ++i) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    used.resize(N);
    sz.resize(N);
    par.resize(N);
    dist.resize(N);
    dfs_sz(0);
    build(centroid(0, -1, sz[0]));
    closest.resize(N, infll);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        int v = X[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            closest[u] = min(closest[u], dist[v][j]);
            u = par[u];
            --j;
        }
    }
    ll ans = infll;
    for (int i = 0; i < T; ++i) {
        int v = Y[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            if (closest[u] < infll) {
                ans = min(ans, closest[u] + dist[v][j]);
            }
            u = par[u];
            --j;
        }
    }
    for (int i = 0; i < S; ++i) {
        int v = X[i];
        int u = v;
        int j = (int) dist[v].size() - 1;
        while (u != -1) {
            closest[u] = infll;
            u = par[u];
            --j;
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 207 ms 9376 KB Output is correct
3 Correct 222 ms 9556 KB Output is correct
4 Correct 216 ms 9548 KB Output is correct
5 Correct 214 ms 9808 KB Output is correct
6 Correct 130 ms 9044 KB Output is correct
7 Correct 208 ms 9500 KB Output is correct
8 Correct 207 ms 9552 KB Output is correct
9 Correct 257 ms 9816 KB Output is correct
10 Correct 140 ms 9088 KB Output is correct
11 Correct 202 ms 9556 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1458 ms 129600 KB Output is correct
3 Correct 2072 ms 165192 KB Output is correct
4 Correct 449 ms 79548 KB Output is correct
5 Correct 2600 ms 213720 KB Output is correct
6 Correct 2167 ms 166224 KB Output is correct
7 Correct 539 ms 35664 KB Output is correct
8 Correct 262 ms 25008 KB Output is correct
9 Correct 644 ms 43328 KB Output is correct
10 Correct 547 ms 36692 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 207 ms 9376 KB Output is correct
3 Correct 222 ms 9556 KB Output is correct
4 Correct 216 ms 9548 KB Output is correct
5 Correct 214 ms 9808 KB Output is correct
6 Correct 130 ms 9044 KB Output is correct
7 Correct 208 ms 9500 KB Output is correct
8 Correct 207 ms 9552 KB Output is correct
9 Correct 257 ms 9816 KB Output is correct
10 Correct 140 ms 9088 KB Output is correct
11 Correct 202 ms 9556 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 1458 ms 129600 KB Output is correct
14 Correct 2072 ms 165192 KB Output is correct
15 Correct 449 ms 79548 KB Output is correct
16 Correct 2600 ms 213720 KB Output is correct
17 Correct 2167 ms 166224 KB Output is correct
18 Correct 539 ms 35664 KB Output is correct
19 Correct 262 ms 25008 KB Output is correct
20 Correct 644 ms 43328 KB Output is correct
21 Correct 547 ms 36692 KB Output is correct
22 Correct 1529 ms 130372 KB Output is correct
23 Correct 1578 ms 133964 KB Output is correct
24 Correct 2464 ms 166936 KB Output is correct
25 Correct 2394 ms 170576 KB Output is correct
26 Correct 2482 ms 167504 KB Output is correct
27 Correct 3067 ms 211928 KB Output is correct
28 Correct 570 ms 83452 KB Output is correct
29 Correct 2481 ms 166996 KB Output is correct
30 Correct 2429 ms 166476 KB Output is correct
31 Correct 2565 ms 166948 KB Output is correct
32 Correct 651 ms 44116 KB Output is correct
33 Correct 219 ms 25544 KB Output is correct
34 Correct 473 ms 31308 KB Output is correct
35 Correct 410 ms 31912 KB Output is correct
36 Correct 559 ms 34332 KB Output is correct
37 Correct 536 ms 34096 KB Output is correct