oj.uz

Submission #630160

# Submission time Handle Problem Language Result Execution time Memory
630160 2022-08-15T19:00:34 Z bebra Factories (JOI14_factories) C++17
100 / 100
 4164 ms 239532 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


const int MAX_N = 500'000;
const int MAX_LOG = 20;
const long long INF = 1e16;
vector<pair<int, int>> g[MAX_N];

int sz[MAX_N];
int level[MAX_N];
bool used[MAX_N];
long long dist[MAX_LOG][MAX_N];
vector<int> centroids[MAX_N];
long long distances[MAX_N];


inline void dfs_calc(int v, int p, int curr_weight, int c) {
    sz[v] = 1;
    if (c != -1) {
        dist[level[c]][v] = dist[level[c]][p] + curr_weight;
        centroids[v].push_back(c);
    }
    for (const auto& [u, weight] : g[v]) {
        if (used[u] || u == p) continue;
        dfs_calc(u, v, weight, c);
        sz[v] += sz[u];
    }
}

inline int find_centroid(int v, int p, int n) {
    for (const auto& [u, w] : g[v]) {
        if (used[u] || u == p) continue;
        if (2 * sz[u] > n) {
            return find_centroid(u, v, n);
        }
    }
    return v;
}

inline void dfs_build(int v = 0, int p = -1, int curr_weight = -1) {
    dfs_calc(v, p, curr_weight, p);
    int c = find_centroid(v, -1, sz[v]);
    if (p != -1) level[c] = level[p] + 1;
    centroids[c].push_back(c);
    used[c] = true;
    for (const auto& [u, weight] : g[c]) {
        if (!used[u]) {
            dfs_build(u, c, weight);
        }
    }
}

inline void add_vertex(int v) {
    for (int c : centroids[v]) {
        distances[c] = min(distances[c], dist[level[c]][v]);
    }
}

inline void remove_vertex(int v) {
    for (int c : centroids[v]) {
        distances[c] = INF;
    }
}

inline long long get_closest(int v) {
    long long res = INF;
    for (int c : centroids[v]) {
        if (distances[c] != INF) {
            res = min(res, dist[level[c]][v] + distances[c]);
        }
    }
    return res;
}

void Init(int n, int a[], int b[], int d[]) {
    for (int i = 0; i < n - 1; ++i) {
        int u = a[i];
        int v = b[i];
        g[u].emplace_back(v, d[i]);
        g[v].emplace_back(u, d[i]);
    }
    fill_n(distances, MAX_N, INF);
    dfs_build();
}

long long Query(int n, int x[], int m, int y[]) {
    for (int i = 0; i < n; ++i) {
        add_vertex(x[i]);
    }
    long long res = INF;
    for (int i = 0; i < m; ++i) {
        res = min(res, get_closest(y[i]));
    }
    for (int i = 0; i < n; ++i) {
        remove_vertex(x[i]);
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28128 KB Output is correct
2 Correct 291 ms 36692 KB Output is correct
3 Correct 322 ms 36864 KB Output is correct
4 Correct 308 ms 36868 KB Output is correct
5 Correct 373 ms 37104 KB Output is correct
6 Correct 207 ms 36208 KB Output is correct
7 Correct 339 ms 36924 KB Output is correct
8 Correct 319 ms 36872 KB Output is correct
9 Correct 343 ms 37064 KB Output is correct
10 Correct 212 ms 36152 KB Output is correct
11 Correct 312 ms 36884 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27852 KB Output is correct
2 Correct 1975 ms 155860 KB Output is correct
3 Correct 2563 ms 188140 KB Output is correct
4 Correct 757 ms 84016 KB Output is correct
5 Correct 3274 ms 214280 KB Output is correct
6 Correct 2673 ms 189440 KB Output is correct
7 Correct 993 ms 63404 KB Output is correct
8 Correct 367 ms 47808 KB Output is correct
9 Correct 1136 ms 68048 KB Output is correct
10 Correct 1014 ms 64812 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 28128 KB Output is correct
2 Correct 291 ms 36692 KB Output is correct
3 Correct 322 ms 36864 KB Output is correct
4 Correct 308 ms 36868 KB Output is correct
5 Correct 373 ms 37104 KB Output is correct
6 Correct 207 ms 36208 KB Output is correct
7 Correct 339 ms 36924 KB Output is correct
8 Correct 319 ms 36872 KB Output is correct
9 Correct 343 ms 37064 KB Output is correct
10 Correct 212 ms 36152 KB Output is correct
11 Correct 312 ms 36884 KB Output is correct
12 Correct 15 ms 27852 KB Output is correct
13 Correct 1975 ms 155860 KB Output is correct
14 Correct 2563 ms 188140 KB Output is correct
15 Correct 757 ms 84016 KB Output is correct
16 Correct 3274 ms 214280 KB Output is correct
17 Correct 2673 ms 189440 KB Output is correct
18 Correct 993 ms 63404 KB Output is correct
19 Correct 367 ms 47808 KB Output is correct
20 Correct 1136 ms 68048 KB Output is correct
21 Correct 1014 ms 64812 KB Output is correct
22 Correct 2504 ms 155868 KB Output is correct
23 Correct 2438 ms 163304 KB Output is correct
24 Correct 3401 ms 193020 KB Output is correct
25 Correct 3458 ms 218188 KB Output is correct
26 Correct 3239 ms 214680 KB Output is correct
27 Correct 4164 ms 239532 KB Output is correct
28 Correct 1128 ms 112644 KB Output is correct
29 Correct 3350 ms 214224 KB Output is correct
30 Correct 3331 ms 214208 KB Output is correct
31 Correct 3207 ms 214472 KB Output is correct
32 Correct 1368 ms 82832 KB Output is correct
33 Correct 415 ms 62224 KB Output is correct
34 Correct 862 ms 71616 KB Output is correct
35 Correct 907 ms 71772 KB Output is correct
36 Correct 1043 ms 75672 KB Output is correct
37 Correct 1036 ms 75756 KB Output is correct