oj.uz

Submission #1110942

# Submission time Handle Problem Language Result Execution time Memory
1110942 2024-11-11T03:43:06 Z LucasLe Factories (JOI14_factories) C++17
100 / 100
 3042 ms 231852 KB 
#include <bits/stdc++.h>

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

int n, q, timeDfs;
int sparse[1000005][LG + 5], par[maxn + 5];
int lg[maxn + 5], 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 <= maxn; ++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; (1 << j) <= timeDfs; ++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 16 ms 57680 KB Output is correct
2 Correct 304 ms 62536 KB Output is correct
3 Correct 433 ms 60020 KB Output is correct
4 Correct 426 ms 59976 KB Output is correct
5 Correct 439 ms 65180 KB Output is correct
6 Correct 173 ms 59976 KB Output is correct
7 Correct 445 ms 59824 KB Output is correct
8 Correct 442 ms 62592 KB Output is correct
9 Correct 448 ms 61768 KB Output is correct
10 Correct 175 ms 59828 KB Output is correct
11 Correct 428 ms 60020 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 55632 KB Output is correct
2 Correct 1194 ms 191556 KB Output is correct
3 Correct 1753 ms 199496 KB Output is correct
4 Correct 539 ms 201904 KB Output is correct
5 Correct 2281 ms 231852 KB Output is correct
6 Correct 1804 ms 199972 KB Output is correct
7 Correct 989 ms 95592 KB Output is correct
8 Correct 276 ms 98748 KB Output is correct
9 Correct 1014 ms 102392 KB Output is correct
10 Correct 987 ms 99560 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 57680 KB Output is correct
2 Correct 304 ms 62536 KB Output is correct
3 Correct 433 ms 60020 KB Output is correct
4 Correct 426 ms 59976 KB Output is correct
5 Correct 439 ms 65180 KB Output is correct
6 Correct 173 ms 59976 KB Output is correct
7 Correct 445 ms 59824 KB Output is correct
8 Correct 442 ms 62592 KB Output is correct
9 Correct 448 ms 61768 KB Output is correct
10 Correct 175 ms 59828 KB Output is correct
11 Correct 428 ms 60020 KB Output is correct
12 Correct 10 ms 55632 KB Output is correct
13 Correct 1194 ms 191556 KB Output is correct
14 Correct 1753 ms 199496 KB Output is correct
15 Correct 539 ms 201904 KB Output is correct
16 Correct 2281 ms 231852 KB Output is correct
17 Correct 1804 ms 199972 KB Output is correct
18 Correct 989 ms 95592 KB Output is correct
19 Correct 276 ms 98748 KB Output is correct
20 Correct 1014 ms 102392 KB Output is correct
21 Correct 987 ms 99560 KB Output is correct
22 Correct 1780 ms 204692 KB Output is correct
23 Correct 1702 ms 206200 KB Output is correct
24 Correct 2576 ms 207516 KB Output is correct
25 Correct 2662 ms 210060 KB Output is correct
26 Correct 2406 ms 201432 KB Output is correct
27 Correct 3042 ms 223544 KB Output is correct
28 Correct 726 ms 201020 KB Output is correct
29 Correct 2571 ms 210168 KB Output is correct
30 Correct 2397 ms 188024 KB Output is correct
31 Correct 2469 ms 201032 KB Output is correct
32 Correct 982 ms 100044 KB Output is correct
33 Correct 297 ms 95828 KB Output is correct
34 Correct 634 ms 94024 KB Output is correct
35 Correct 633 ms 94192 KB Output is correct
36 Correct 943 ms 87624 KB Output is correct
37 Correct 915 ms 94536 KB Output is correct