oj.uz

Submission #754803

# Submission time Handle Problem Language Result Execution time Memory
754803 2023-06-08T15:08:20 Z Desh03 Factories (JOI14_factories) C++17
100 / 100
 5103 ms 171520 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
vector<long long> d, mn;
vector<int> dep, out, sz, par, euler;
vector<bool> centroid;
vector<vector<pair<int, int>>> g;

void dfs(int u, int p) {
    out[u] = euler.size();
    euler.push_back(u);
    for (auto [v, w] : g[u])
        if (v ^ p) {
            d[v] = d[u] + w;
            dep[v] = dep[u] + 1;
            dfs(v, u);
            out[u] = euler.size();
            euler.push_back(u);
        }
}

struct RMQ {
    vector<vector<int>> sparse;
    vector<int> lg;
    int comp(const int &a, const int &b) {
        return dep[a] < dep[b] ? a : b;
    }
    void init(const vector<int> &v) {
        int n = v.size();
        lg.resize(n + 1);
        for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
        sparse = vector<vector<int>> (lg[n] + 1, vector<int> (n));
        for (int i = 0; i < n; i++) sparse[0][i] = v[i];
        for (int i = 1; i <= lg[n]; i++)
            for (int j = 0; j + (1 << (i - 1)) < n; j++)
                sparse[i][j] = comp(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]);
    }
    int query(int l, int r) {
        return comp(sparse[lg[r - l + 1]][l], sparse[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]);
    }
} rmq;

int lca(int u, int v) {
    if (out[u] > out[v]) swap(u, v);
    return rmq.query(out[u], out[v]);
}

long long dist(int u, int v) {
    return d[u] + d[v] - (d[lca(u, v)] << 1);
}

int findcentroid(int u, int p, int root) {
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v] && sz[v] << 1 > sz[root])
            return findcentroid(v, u, root);
    return u;
}

void calcsz(int u, int p) {
    sz[u] = 1;
    for (auto [v, w] : g[u])
        if (v ^ p && !centroid[v])
            calcsz(v, u), sz[u] += sz[v];
}

int centroid_decompose(int u) {
    calcsz(u, u);
    int x = findcentroid(u, u, u);
    centroid[x] = 1;
    for (auto [v, w] : g[x])
        if (!centroid[v])
            par[centroid_decompose(v)] = x;
    return x;
}

void update(int u) {
    int x = u;
    while (u != -1) {
        mn[u] = min(mn[u], dist(x, u));
        u = par[u];
    }
}

void reset(int u) {
    while (u != -1) {
        mn[u] = INF;
        u = par[u];
    }
}

long long qry(int u) {
    int x = u;
    long long ret = INF;
    while (u != -1) {
        ret = min(ret, mn[u] + dist(x, u));
        u = par[u];
    }
    return ret;
}

void Init(int n, int a[], int b[], int c[]) {
    g.resize(n), d.resize(n), dep.resize(n), sz.resize(n), par.resize(n, -1), mn.resize(n, INF), centroid.resize(n), out.resize(n);
    for (int i = 0; i < n - 1; i++) {
        g[a[i]].push_back({b[i], c[i]});
        g[b[i]].push_back({a[i], c[i]});
    }
    dfs(0, 0);
    rmq.init(euler);
    centroid_decompose(0);
}

long long Query(int s, int x[], int t, int y[]) {
    for (int i = 0; i < s; i++) update(x[i]);
    long long ans = INF;
    for (int i = 0; i < t; i++) ans = min(ans, qry(y[i]));
    for (int i = 0; i < s; i++)
        if (mn[x[i]] != INF) reset(x[i]);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 332 ms 9436 KB Output is correct
3 Correct 396 ms 9404 KB Output is correct
4 Correct 450 ms 9624 KB Output is correct
5 Correct 449 ms 9676 KB Output is correct
6 Correct 202 ms 9424 KB Output is correct
7 Correct 382 ms 9588 KB Output is correct
8 Correct 404 ms 9728 KB Output is correct
9 Correct 450 ms 9676 KB Output is correct
10 Correct 198 ms 9420 KB Output is correct
11 Correct 399 ms 9724 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1897 ms 147768 KB Output is correct
3 Correct 2768 ms 150000 KB Output is correct
4 Correct 701 ms 148500 KB Output is correct
5 Correct 3735 ms 171520 KB Output is correct
6 Correct 2842 ms 150288 KB Output is correct
7 Correct 1509 ms 36284 KB Output is correct
8 Correct 356 ms 37028 KB Output is correct
9 Correct 1653 ms 39832 KB Output is correct
10 Correct 1521 ms 37600 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 332 ms 9436 KB Output is correct
3 Correct 396 ms 9404 KB Output is correct
4 Correct 450 ms 9624 KB Output is correct
5 Correct 449 ms 9676 KB Output is correct
6 Correct 202 ms 9424 KB Output is correct
7 Correct 382 ms 9588 KB Output is correct
8 Correct 404 ms 9728 KB Output is correct
9 Correct 450 ms 9676 KB Output is correct
10 Correct 198 ms 9420 KB Output is correct
11 Correct 399 ms 9724 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 1897 ms 147768 KB Output is correct
14 Correct 2768 ms 150000 KB Output is correct
15 Correct 701 ms 148500 KB Output is correct
16 Correct 3735 ms 171520 KB Output is correct
17 Correct 2842 ms 150288 KB Output is correct
18 Correct 1509 ms 36284 KB Output is correct
19 Correct 356 ms 37028 KB Output is correct
20 Correct 1653 ms 39832 KB Output is correct
21 Correct 1521 ms 37600 KB Output is correct
22 Correct 2846 ms 150364 KB Output is correct
23 Correct 2865 ms 151128 KB Output is correct
24 Correct 4123 ms 152512 KB Output is correct
25 Correct 4477 ms 153836 KB Output is correct
26 Correct 4114 ms 153128 KB Output is correct
27 Correct 5103 ms 169144 KB Output is correct
28 Correct 970 ms 151964 KB Output is correct
29 Correct 3984 ms 152524 KB Output is correct
30 Correct 4213 ms 152064 KB Output is correct
31 Correct 4154 ms 152620 KB Output is correct
32 Correct 1854 ms 40764 KB Output is correct
33 Correct 356 ms 37368 KB Output is correct
34 Correct 1113 ms 35112 KB Output is correct
35 Correct 1006 ms 35168 KB Output is correct
36 Correct 1462 ms 35624 KB Output is correct
37 Correct 1475 ms 35680 KB Output is correct