oj.uz

Submission #422658

# Submission time Handle Problem Language Result Execution time Memory
422658 2021-06-10T09:37:22 Z tengiz05 Factories (JOI14_factories) C++17
100 / 100
 7341 ms 336324 KB 
#pragma GCC optimize("O3,Ofast")
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 21, M = 2 * N + 1;
std::vector<std::pair<int, int>> e[N];
i64 st[K + 1][M];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
int order[N], timeStamp;
int par[N];
int dpar[N];
void dfs(int u, int p, i64 d = 0){
    order[timeStamp++] = u;
    par[u] = p;
    P[u] = timer;
    pos[timer++] = d;
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dpar[v] = w;
            dfs(v, u, d + w);
            pos[timer++] = d;
        }
    }
}
inline i64 dist(int u, int v) {
    int L = P[u], R = P[v];
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    return D[u] + D[v] - std::min(st[j][L], st[j][R - (1 << j) + 1]);
}
bool vis[N];
int siz[N], now;
std::vector<int> have;
void calc_s(int u, int p) {
    have.push_back(u);
    siz[u] = 1;
    for (auto [v, w] : e[u]) {
        if (!vis[v] && v != p) {
            calc_s(v, u);
            siz[u] += siz[v];
        }
    }
}
int centroid(int u, int p) {
    for (auto [v, w] : e[u]) {
        if (!vis[v] && v != p && siz[v] > now / 2) {
            return centroid(v, u);
        }
    }
    return u;
}
std::vector<int> cpar[N];
void decompose(int u) {
    have.clear();
    calc_s(u, u);
    now = siz[u];
    u = centroid(u, u);
    vis[u] = true;
    for (auto x : have) {
        cpar[x].push_back(u);
    }
    for (auto [v, w] : e[u]) {
        if (!vis[v]) {
            decompose(v);
        }
    } 
}
i64 dp[N];
i64 res[N];
void Init(int n, int A[], int B[], int D[]) {
    memset(res, 0x3f, sizeof res);
    lg[1] = 0;
    for (int i = 2; i <= M; i++)
        lg[i] = lg[i / 2] + 1;
    ::n = n;
    for (int i = 0; i < n - 1; i++) {
        e[A[i]].emplace_back(B[i], D[i]);
        e[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0);
    for (int i = 0; i < M; i++)
        st[0][i] = 2 * pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= M; i++)
            st[j][i] = std::min(st[j-1][i], st[j - 1][i + (1 << (j - 1))]);
    std::cerr << "fu";
    decompose(0);
    std::cerr << "ck\n";
}
i64 Query(int S, int X[], int T, int Y[]) {
    std::vector<int> changed;
    for (int i = 0; i < S; i++) {
        int u = X[i];
        for (auto v : cpar[u]) {
            changed.push_back(v);
            res[v] = std::min(res[v], dist(u, v));
        }
    }
    i64 ans = 1e17;
    for (int i = 0; i < T; i++) {
        int u = Y[i];
        for (auto v : cpar[u]) {
            ans = std::min(ans, res[v] + dist(u, v));
        }
    }
    for (auto x : changed) {
        res[x] = 1e17;
    }
    return ans;
    // memset(dp, 0x3f, sizeof dp);
    // for (int i = 0; i < S; i++) {
    //     dp[X[i]] = 0;
    // }
    // for (int i = n - 1; i >= 0; i--) {
    //     int u = order[i];
    //     dp[par[u]] = std::min(dp[par[u]], dp[u] + dpar[u]);
    // }
    // for (int i = 0; i < n; i++) {
    //     int u = order[i];
    //     dp[u] = std::min(dp[u], dp[par[u]] + dpar[u]);
    // }
    // i64 ans =  1e16;
    // for (int i = 0; i < T; i++) {
    //     ans = std::min(ans, dp[Y[i]]);
    // }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 180420 KB Output is correct
2 Correct 576 ms 188876 KB Output is correct
3 Correct 697 ms 189040 KB Output is correct
4 Correct 712 ms 189472 KB Output is correct
5 Correct 746 ms 189420 KB Output is correct
6 Correct 405 ms 188696 KB Output is correct
7 Correct 651 ms 188916 KB Output is correct
8 Correct 699 ms 188980 KB Output is correct
9 Correct 811 ms 189508 KB Output is correct
10 Correct 397 ms 188892 KB Output is correct
11 Correct 671 ms 188916 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 180164 KB Output is correct
2 Correct 3504 ms 272660 KB Output is correct
3 Correct 4507 ms 292120 KB Output is correct
4 Correct 1392 ms 251860 KB Output is correct
5 Correct 5518 ms 334208 KB Output is correct
6 Correct 4542 ms 293224 KB Output is correct
7 Correct 2424 ms 207548 KB Output is correct
8 Correct 918 ms 203516 KB Output is correct
9 Correct 2976 ms 213816 KB Output is correct
10 Correct 2533 ms 209028 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 180420 KB Output is correct
2 Correct 576 ms 188876 KB Output is correct
3 Correct 697 ms 189040 KB Output is correct
4 Correct 712 ms 189472 KB Output is correct
5 Correct 746 ms 189420 KB Output is correct
6 Correct 405 ms 188696 KB Output is correct
7 Correct 651 ms 188916 KB Output is correct
8 Correct 699 ms 188980 KB Output is correct
9 Correct 811 ms 189508 KB Output is correct
10 Correct 397 ms 188892 KB Output is correct
11 Correct 671 ms 188916 KB Output is correct
12 Correct 108 ms 180164 KB Output is correct
13 Correct 3504 ms 272660 KB Output is correct
14 Correct 4507 ms 292120 KB Output is correct
15 Correct 1392 ms 251860 KB Output is correct
16 Correct 5518 ms 334208 KB Output is correct
17 Correct 4542 ms 293224 KB Output is correct
18 Correct 2424 ms 207548 KB Output is correct
19 Correct 918 ms 203516 KB Output is correct
20 Correct 2976 ms 213816 KB Output is correct
21 Correct 2533 ms 209028 KB Output is correct
22 Correct 4232 ms 277540 KB Output is correct
23 Correct 4366 ms 282764 KB Output is correct
24 Correct 5878 ms 300972 KB Output is correct
25 Correct 6245 ms 302488 KB Output is correct
26 Correct 6161 ms 294352 KB Output is correct
27 Correct 7341 ms 336324 KB Output is correct
28 Correct 1763 ms 256808 KB Output is correct
29 Correct 5933 ms 293848 KB Output is correct
30 Correct 5920 ms 293164 KB Output is correct
31 Correct 6048 ms 293796 KB Output is correct
32 Correct 2957 ms 219776 KB Output is correct
33 Correct 990 ms 204228 KB Output is correct
34 Correct 1869 ms 204604 KB Output is correct
35 Correct 1899 ms 204760 KB Output is correct
36 Correct 2451 ms 206460 KB Output is correct
37 Correct 2351 ms 206356 KB Output is correct