oj.uz

Submission #1110934

# Submission time Handle Problem Language Result Execution time Memory
1110934 2024-11-11T03:36:03 Z LucasLe Factories (JOI14_factories) C++17
100 / 100
 2851 ms 236256 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] - 2ll * 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];
        int v = B[i];
        int w = D[i];
        u++, v++;
        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 334 ms 60232 KB Output is correct
3 Correct 489 ms 69448 KB Output is correct
4 Correct 450 ms 69540 KB Output is correct
5 Correct 443 ms 69704 KB Output is correct
6 Correct 174 ms 69448 KB Output is correct
7 Correct 478 ms 69276 KB Output is correct
8 Correct 471 ms 69400 KB Output is correct
9 Correct 419 ms 69960 KB Output is correct
10 Correct 168 ms 69448 KB Output is correct
11 Correct 412 ms 69484 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 1396 ms 205528 KB Output is correct
3 Correct 2099 ms 210760 KB Output is correct
4 Correct 601 ms 205920 KB Output is correct
5 Correct 2613 ms 236256 KB Output is correct
6 Correct 1818 ms 211356 KB Output is correct
7 Correct 1028 ms 102160 KB Output is correct
8 Correct 281 ms 102076 KB Output is correct
9 Correct 1012 ms 105632 KB Output is correct
10 Correct 1132 ms 102672 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 334 ms 60232 KB Output is correct
3 Correct 489 ms 69448 KB Output is correct
4 Correct 450 ms 69540 KB Output is correct
5 Correct 443 ms 69704 KB Output is correct
6 Correct 174 ms 69448 KB Output is correct
7 Correct 478 ms 69276 KB Output is correct
8 Correct 471 ms 69400 KB Output is correct
9 Correct 419 ms 69960 KB Output is correct
10 Correct 168 ms 69448 KB Output is correct
11 Correct 412 ms 69484 KB Output is correct
12 Correct 10 ms 55632 KB Output is correct
13 Correct 1396 ms 205528 KB Output is correct
14 Correct 2099 ms 210760 KB Output is correct
15 Correct 601 ms 205920 KB Output is correct
16 Correct 2613 ms 236256 KB Output is correct
17 Correct 1818 ms 211356 KB Output is correct
18 Correct 1028 ms 102160 KB Output is correct
19 Correct 281 ms 102076 KB Output is correct
20 Correct 1012 ms 105632 KB Output is correct
21 Correct 1132 ms 102672 KB Output is correct
22 Correct 1567 ms 212640 KB Output is correct
23 Correct 1785 ms 211844 KB Output is correct
24 Correct 2426 ms 213272 KB Output is correct
25 Correct 2530 ms 215696 KB Output is correct
26 Correct 2484 ms 215264 KB Output is correct
27 Correct 2851 ms 235464 KB Output is correct
28 Correct 733 ms 213680 KB Output is correct
29 Correct 2398 ms 213452 KB Output is correct
30 Correct 2511 ms 212248 KB Output is correct
31 Correct 2316 ms 215540 KB Output is correct
32 Correct 984 ms 106732 KB Output is correct
33 Correct 303 ms 102492 KB Output is correct
34 Correct 606 ms 100620 KB Output is correct
35 Correct 645 ms 100644 KB Output is correct
36 Correct 926 ms 101348 KB Output is correct
37 Correct 892 ms 101460 KB Output is correct