oj.uz

Submission #1110944

# Submission time Handle Problem Language Result Execution time Memory
1110944 2024-11-11T03:46:59 Z LucasLe Factories (JOI14_factories) C++17
100 / 100
 3036 ms 203200 KB 
#include <bits/stdc++.h>

const int maxn = 5e5 + 5;
const int LG = 20;
const long long INF = 1e17;

int n, q, timeDfs;
int sparse[1000005][LG + 5], par[maxn + 5];
int lg[1000005], sz[maxn + 5], h[maxn + 5], tin[maxn + 5];

long long depth[maxn + 5], d[maxn + 5];

bool del[maxn + 5];

std::vector<int> nd;
std::vector<std::pair<int, int>> g[maxn + 5];

void init() {
    for (int i = 2; i <= 1000000; ++i)
        lg[i] = lg[i / 2] + 1;
}

int combine(int u, int v) {
    return h[u] < h[v] ? u : v;
}

void dfs(int u, int p) {
    sparse[++timeDfs][0] = u;
    tin[u] = timeDfs;
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        int w = tmp.second;
        if (v == p) continue;
        depth[v] = depth[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
        sparse[++timeDfs][0] = u; 
    }
}

int find_centroid(int u, int p, int m) {
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        if (del[v] || v == p) continue;
        if (sz[v] > m / 2) return find_centroid(v, u, m);
    }
    return u;
}

void reset_sz(int u, int p) {
    sz[u] = 1;
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        if (del[v] || v == p) continue;
        reset_sz(v, u);
        sz[u] += sz[v];
    }
}

long long dist(int u, int v) {
    if (tin[u] > tin[v]) std::swap(u, v);
    int base = lg[tin[v] - tin[u] + 1];
    int lca = combine(sparse[tin[u]][base], sparse[tin[v] - (1 << base) + 1][base]);
    return depth[u] + depth[v] - 2 * depth[lca];
}

int CD(int u) {
    reset_sz(u, 0);
    int cen = find_centroid(u, 0, sz[u]);
    del[cen] = true;
    for (std::pair<int, int> tmp : g[cen]) {
        int v = tmp.first;
        if (del[v]) continue;
        par[CD(v)] = cen;
    }
    return cen;
}

void update(int u) {
    int anc = u;
    while (anc) {
        d[anc] = std::min(d[anc], dist(u, anc));
        anc = par[anc];
    }
}

long long query(int u) {
    int anc = u;
    long long ans = INF;
    while (anc) {
        ans = std::min(ans, dist(u, anc) + d[anc]);
        anc = par[anc];
    }
    return ans;
}

void init_d(int u) {
    int anc = u;
    while (anc) {
        d[anc] = INF;
        anc = par[anc];
    }
} 

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i <= n - 2; ++i) {
        int u = A[i] + 1;
        int v = B[i] + 1;
        int w = D[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0);
    for (int j = 1; j <= LG; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= timeDfs; ++i) {
            sparse[i][j] = combine(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
        }
    }
    CD(1);
    init();
    for (int i = 1; i <= n; ++i) d[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; ++i) {
        int u = X[i] + 1;
        nd.push_back(u);
        update(u);
    }
    long long ans = INF;
    for (int i = 0; i < T; ++i) {
        int u = Y[i] + 1;
        ans = std::min(ans, query(u));
    }
    for (int u : nd) 
        init_d(u);
    nd.clear();
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 40528 KB Output is correct
2 Correct 302 ms 44920 KB Output is correct
3 Correct 441 ms 46816 KB Output is correct
4 Correct 399 ms 44872 KB Output is correct
5 Correct 423 ms 45228 KB Output is correct
6 Correct 162 ms 44972 KB Output is correct
7 Correct 434 ms 44976 KB Output is correct
8 Correct 460 ms 44952 KB Output is correct
9 Correct 486 ms 45128 KB Output is correct
10 Correct 187 ms 44872 KB Output is correct
11 Correct 494 ms 44936 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 40528 KB Output is correct
2 Correct 1456 ms 169972 KB Output is correct
3 Correct 2248 ms 173624 KB Output is correct
4 Correct 553 ms 181680 KB Output is correct
5 Correct 2533 ms 203200 KB Output is correct
6 Correct 2012 ms 173640 KB Output is correct
7 Correct 1004 ms 73400 KB Output is correct
8 Correct 307 ms 74940 KB Output is correct
9 Correct 971 ms 76652 KB Output is correct
10 Correct 1080 ms 77132 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 40528 KB Output is correct
2 Correct 302 ms 44920 KB Output is correct
3 Correct 441 ms 46816 KB Output is correct
4 Correct 399 ms 44872 KB Output is correct
5 Correct 423 ms 45228 KB Output is correct
6 Correct 162 ms 44972 KB Output is correct
7 Correct 434 ms 44976 KB Output is correct
8 Correct 460 ms 44952 KB Output is correct
9 Correct 486 ms 45128 KB Output is correct
10 Correct 187 ms 44872 KB Output is correct
11 Correct 494 ms 44936 KB Output is correct
12 Correct 8 ms 40528 KB Output is correct
13 Correct 1456 ms 169972 KB Output is correct
14 Correct 2248 ms 173624 KB Output is correct
15 Correct 553 ms 181680 KB Output is correct
16 Correct 2533 ms 203200 KB Output is correct
17 Correct 2012 ms 173640 KB Output is correct
18 Correct 1004 ms 73400 KB Output is correct
19 Correct 307 ms 74940 KB Output is correct
20 Correct 971 ms 76652 KB Output is correct
21 Correct 1080 ms 77132 KB Output is correct
22 Correct 1820 ms 169772 KB Output is correct
23 Correct 1902 ms 170688 KB Output is correct
24 Correct 2277 ms 182032 KB Output is correct
25 Correct 2307 ms 174280 KB Output is correct
26 Correct 2357 ms 178848 KB Output is correct
27 Correct 3036 ms 194160 KB Output is correct
28 Correct 689 ms 171644 KB Output is correct
29 Correct 2427 ms 184320 KB Output is correct
30 Correct 2367 ms 171324 KB Output is correct
31 Correct 2476 ms 178184 KB Output is correct
32 Correct 941 ms 77728 KB Output is correct
33 Correct 313 ms 77252 KB Output is correct
34 Correct 758 ms 72008 KB Output is correct
35 Correct 625 ms 72188 KB Output is correct
36 Correct 964 ms 72824 KB Output is correct
37 Correct 959 ms 72808 KB Output is correct