oj.uz

Submission #853785

# Submission time Handle Problem Language Result Execution time Memory
853785 2023-09-25T08:36:48 Z anha3k25cvp Factories (JOI14_factories) C++14
100 / 100
 4990 ms 283392 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "factories.h"

using namespace std;

const ll inf = 7 + 1e18;

int n, logn, tsize;
vector <int> sz, pa, h;
vector <ll> f, ans;
vector <vector <int>> p;
vector <vector <II>> adj;

///--------------------------LCA-------------------------------

void dfs_lca(int u) {
    for (auto z : adj[u]) {
        int v = z.st;
        ll w = z.nd;
        if (h[v])
            continue;
        h[v] = h[u] + 1;
        f[v] = f[u] + w;
        p[0][v] = u;
        dfs_lca(v);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v])
        swap(u, v);
    int d = h[u] - h[v];
    for (int si = d; si > 0; si ^= si & -si) {
        int i = __builtin_ctz(si & -si);
        u = p[i][u];
    }
    if (u == v)
        return u;
    for (int i = logn - 1; i >= 0; i --)
        if (p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
    return p[0][u];
}

ll dis(int u, int v) {
    return f[u] + f[v] - f[lca(u, v)] * 2;
}

///-------------------------CENTROID-----------------------------

void dfs(int u, int p) {
    tsize ++;
    sz[u] = 1;
    for (auto z : adj[u]) {
        int v = z.st;
        if (v == p || pa[v])
            continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p) {
    for (auto z : adj[u]) {
        int v = z.st;
        if (v == p || pa[v])
            continue;
        if (sz[v] * 2 > tsize)
            return centroid(v, u);
    }
    return u;
}

void build(int u, int p) {
    tsize = 0;
    dfs(u, 0);
    int c = centroid(u, 0);
    if (p == 0)
        pa[c] = c;
    else
        pa[c] = p;
    for (auto z : adj[c]) {
        int v = z.st;
        if (pa[v])
            continue;
        build(v, c);
    }
}

vector <vector <ll>> dist;

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    adj.resize(n + 1);
    for (int i = 0; i < n - 1; i ++) {
        A[i] ++; B[i] ++;
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    for (logn = 1; (1 << logn) <= n; logn ++);
    h.assign(n + 1, 0);
    p.assign(logn, vector <int> (n + 1, 0));
    f.assign(n + 1, 0);
    h[1] = 1;
    dfs_lca(1);
    for (int i = 1; i < logn; i ++)
        for (int u = 1; u <= n; u ++)
            p[i][u] = p[i - 1][p[i - 1][u]];
    sz.assign(n + 1, 0);
    pa.assign(n + 1, 0);
    build(1, 0);
    ans.assign(n + 1, inf);
    dist.resize(n + 1);
    for (int u = 1; u <= n; u ++)
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            dist[u].push_back(dis(v, u));
        }
}

long long Query(int S, int X[], int T, int Y[]) {
    vector <int> del;
    ll res = inf;
    for (int i = 0; i < S; i ++) {
        int u = X[i] + 1, cnt = 0;
        if (ans[u] == inf)
            del.push_back(u);
        ans[u] = 0;
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            if (ans[v] == inf)
                del.push_back(v);
            ans[v] = min(ans[v], dist[u][cnt]);
            del.push_back(v);
            cnt ++;
        }
    }
    for (int i = 0; i < T; i ++) {
        int u = Y[i] + 1, cnt = 0;
        res = min(res, ans[u]);
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            res = min(res, dist[u][cnt] + ans[v]);
            cnt ++;
        }
    }
    for (int u : del)
        ans[u] = inf;
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 210 ms 22092 KB Output is correct
3 Correct 233 ms 22352 KB Output is correct
4 Correct 233 ms 22728 KB Output is correct
5 Correct 247 ms 22884 KB Output is correct
6 Correct 155 ms 21840 KB Output is correct
7 Correct 229 ms 22352 KB Output is correct
8 Correct 232 ms 22612 KB Output is correct
9 Correct 253 ms 23160 KB Output is correct
10 Correct 155 ms 22096 KB Output is correct
11 Correct 230 ms 22352 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 1989 ms 178004 KB Output is correct
3 Correct 3809 ms 200700 KB Output is correct
4 Correct 536 ms 133372 KB Output is correct
5 Correct 4632 ms 257524 KB Output is correct
6 Correct 3884 ms 200760 KB Output is correct
7 Correct 704 ms 53960 KB Output is correct
8 Correct 241 ms 42948 KB Output is correct
9 Correct 772 ms 56944 KB Output is correct
10 Correct 713 ms 54472 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 210 ms 22092 KB Output is correct
3 Correct 233 ms 22352 KB Output is correct
4 Correct 233 ms 22728 KB Output is correct
5 Correct 247 ms 22884 KB Output is correct
6 Correct 155 ms 21840 KB Output is correct
7 Correct 229 ms 22352 KB Output is correct
8 Correct 232 ms 22612 KB Output is correct
9 Correct 253 ms 23160 KB Output is correct
10 Correct 155 ms 22096 KB Output is correct
11 Correct 230 ms 22352 KB Output is correct
12 Correct 4 ms 16728 KB Output is correct
13 Correct 1989 ms 178004 KB Output is correct
14 Correct 3809 ms 200700 KB Output is correct
15 Correct 536 ms 133372 KB Output is correct
16 Correct 4632 ms 257524 KB Output is correct
17 Correct 3884 ms 200760 KB Output is correct
18 Correct 704 ms 53960 KB Output is correct
19 Correct 241 ms 42948 KB Output is correct
20 Correct 772 ms 56944 KB Output is correct
21 Correct 713 ms 54472 KB Output is correct
22 Correct 2180 ms 183148 KB Output is correct
23 Correct 2308 ms 185656 KB Output is correct
24 Correct 4271 ms 206896 KB Output is correct
25 Correct 4247 ms 231716 KB Output is correct
26 Correct 4252 ms 224928 KB Output is correct
27 Correct 4990 ms 283392 KB Output is correct
28 Correct 667 ms 158852 KB Output is correct
29 Correct 4219 ms 223920 KB Output is correct
30 Correct 4239 ms 223020 KB Output is correct
31 Correct 4183 ms 223688 KB Output is correct
32 Correct 831 ms 77696 KB Output is correct
33 Correct 258 ms 57864 KB Output is correct
34 Correct 461 ms 62664 KB Output is correct
35 Correct 456 ms 63176 KB Output is correct
36 Correct 669 ms 67016 KB Output is correct
37 Correct 682 ms 67276 KB Output is correct