oj.uz

Submission #754775

# Submission time Handle Problem Language Result Execution time Memory
754775 2023-06-08T14:00:46 Z Desh03 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 95384 KB 
#include <bits/stdc++.h>
using namespace std;

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

void dfs(int u) {
    for (int i = 1; i < lg; i++) up[i][u] = up[i - 1][up[i - 1][u]];
    for (auto [v, w] : g[u])
        if (v ^ up[0][u])
            d[v] = d[u] + w, dep[v] = dep[u] + 1, up[0][v] = u, dfs(v);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for (int i = 0; i < lg; i++)
        if (k >> i & 1)
            u = up[i][u];
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--)
        if (up[i][u] ^ up[i][v])
            u = up[i][u], v = up[i][v];
    return up[0][u];
}

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[]) {
    while ((1 << lg) <= n) ++lg;
    g.resize(n), d.resize(n), dep.resize(n), sz.resize(n), par.resize(n, -1), mn.resize(n, INF), centroid.resize(n);
    up = vector<vector<int>> (lg, vector<int> (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);
    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 12 ms 836 KB Output is correct
2 Correct 662 ms 8976 KB Output is correct
3 Correct 1196 ms 18564 KB Output is correct
4 Correct 1213 ms 18696 KB Output is correct
5 Correct 1353 ms 18884 KB Output is correct
6 Correct 230 ms 18656 KB Output is correct
7 Correct 1273 ms 18432 KB Output is correct
8 Correct 1259 ms 18544 KB Output is correct
9 Correct 1352 ms 18892 KB Output is correct
10 Correct 273 ms 18468 KB Output is correct
11 Correct 1175 ms 18464 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4282 ms 94480 KB Output is correct
3 Execution timed out 8079 ms 95384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 836 KB Output is correct
2 Correct 662 ms 8976 KB Output is correct
3 Correct 1196 ms 18564 KB Output is correct
4 Correct 1213 ms 18696 KB Output is correct
5 Correct 1353 ms 18884 KB Output is correct
6 Correct 230 ms 18656 KB Output is correct
7 Correct 1273 ms 18432 KB Output is correct
8 Correct 1259 ms 18544 KB Output is correct
9 Correct 1352 ms 18892 KB Output is correct
10 Correct 273 ms 18468 KB Output is correct
11 Correct 1175 ms 18464 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 4282 ms 94480 KB Output is correct
14 Execution timed out 8079 ms 95384 KB Time limit exceeded
15 Halted 0 ms 0 KB -