oj.uz

Submission #754801

# Submission time Handle Problem Language Result Execution time Memory
754801 2023-06-08T15:03:46 Z Desh03 Factories (JOI14_factories) C++17
100 / 100
 5196 ms 193956 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++) reset(x[i]);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 327 ms 9400 KB Output is correct
3 Correct 432 ms 9388 KB Output is correct
4 Correct 405 ms 9700 KB Output is correct
5 Correct 473 ms 9676 KB Output is correct
6 Correct 201 ms 9448 KB Output is correct
7 Correct 435 ms 9396 KB Output is correct
8 Correct 407 ms 9492 KB Output is correct
9 Correct 468 ms 9676 KB Output is correct
10 Correct 221 ms 9464 KB Output is correct
11 Correct 478 ms 9600 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2211 ms 147728 KB Output is correct
3 Correct 2773 ms 150072 KB Output is correct
4 Correct 698 ms 148400 KB Output is correct
5 Correct 3709 ms 171560 KB Output is correct
6 Correct 3012 ms 150388 KB Output is correct
7 Correct 1551 ms 36276 KB Output is correct
8 Correct 346 ms 36996 KB Output is correct
9 Correct 1717 ms 39848 KB Output is correct
10 Correct 1393 ms 37684 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 327 ms 9400 KB Output is correct
3 Correct 432 ms 9388 KB Output is correct
4 Correct 405 ms 9700 KB Output is correct
5 Correct 473 ms 9676 KB Output is correct
6 Correct 201 ms 9448 KB Output is correct
7 Correct 435 ms 9396 KB Output is correct
8 Correct 407 ms 9492 KB Output is correct
9 Correct 468 ms 9676 KB Output is correct
10 Correct 221 ms 9464 KB Output is correct
11 Correct 478 ms 9600 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2211 ms 147728 KB Output is correct
14 Correct 2773 ms 150072 KB Output is correct
15 Correct 698 ms 148400 KB Output is correct
16 Correct 3709 ms 171560 KB Output is correct
17 Correct 3012 ms 150388 KB Output is correct
18 Correct 1551 ms 36276 KB Output is correct
19 Correct 346 ms 36996 KB Output is correct
20 Correct 1717 ms 39848 KB Output is correct
21 Correct 1393 ms 37684 KB Output is correct
22 Correct 2832 ms 174820 KB Output is correct
23 Correct 2851 ms 175880 KB Output is correct
24 Correct 4408 ms 176880 KB Output is correct
25 Correct 4338 ms 178564 KB Output is correct
26 Correct 4204 ms 177240 KB Output is correct
27 Correct 5196 ms 193956 KB Output is correct
28 Correct 974 ms 176616 KB Output is correct
29 Correct 4243 ms 176820 KB Output is correct
30 Correct 3920 ms 176468 KB Output is correct
31 Correct 4000 ms 176948 KB Output is correct
32 Correct 1592 ms 54796 KB Output is correct
33 Correct 404 ms 51356 KB Output is correct
34 Correct 1054 ms 48704 KB Output is correct
35 Correct 1099 ms 48620 KB Output is correct
36 Correct 1276 ms 49220 KB Output is correct
37 Correct 1457 ms 49220 KB Output is correct