oj.uz

Submission #853754

# Submission time Handle Problem Language Result Execution time Memory
853754 2023-09-25T07:41:21 Z anha3k25cvp Factories (JOI14_factories) C++14
33 / 100
 8000 ms 129196 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);
    }
}

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);
}

long long Query(int S, int X[], int T, int Y[]) {
    vector <int> del;
    for (int i = 0; i < S; i ++) {
        int u = X[i] + 1;
        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], dis(v, u));
            del.push_back(v);
        }
    }
    ll res = inf;
    for (int i = 0; i < T; i ++) {
        int u = Y[i] + 1;
        res = min(res, ans[u]);
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            res = min(res, dis(v, u) + ans[v]);
        }
    }
    for (int u : del)
        ans[u] = inf;
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16988 KB Output is correct
2 Correct 336 ms 26616 KB Output is correct
3 Correct 682 ms 26960 KB Output is correct
4 Correct 623 ms 26920 KB Output is correct
5 Correct 639 ms 26988 KB Output is correct
6 Correct 147 ms 26452 KB Output is correct
7 Correct 676 ms 26556 KB Output is correct
8 Correct 678 ms 26704 KB Output is correct
9 Correct 626 ms 27260 KB Output is correct
10 Correct 146 ms 26536 KB Output is correct
11 Correct 670 ms 26968 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16732 KB Output is correct
2 Correct 2341 ms 114484 KB Output is correct
3 Correct 5219 ms 107800 KB Output is correct
4 Correct 444 ms 105708 KB Output is correct
5 Correct 5944 ms 129196 KB Output is correct
6 Correct 5830 ms 107896 KB Output is correct
7 Correct 3126 ms 37768 KB Output is correct
8 Correct 251 ms 37688 KB Output is correct
9 Correct 2184 ms 40364 KB Output is correct
10 Correct 2787 ms 38196 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16988 KB Output is correct
2 Correct 336 ms 26616 KB Output is correct
3 Correct 682 ms 26960 KB Output is correct
4 Correct 623 ms 26920 KB Output is correct
5 Correct 639 ms 26988 KB Output is correct
6 Correct 147 ms 26452 KB Output is correct
7 Correct 676 ms 26556 KB Output is correct
8 Correct 678 ms 26704 KB Output is correct
9 Correct 626 ms 27260 KB Output is correct
10 Correct 146 ms 26536 KB Output is correct
11 Correct 670 ms 26968 KB Output is correct
12 Correct 3 ms 16732 KB Output is correct
13 Correct 2341 ms 114484 KB Output is correct
14 Correct 5219 ms 107800 KB Output is correct
15 Correct 444 ms 105708 KB Output is correct
16 Correct 5944 ms 129196 KB Output is correct
17 Correct 5830 ms 107896 KB Output is correct
18 Correct 3126 ms 37768 KB Output is correct
19 Correct 251 ms 37688 KB Output is correct
20 Correct 2184 ms 40364 KB Output is correct
21 Correct 2787 ms 38196 KB Output is correct
22 Correct 3631 ms 110284 KB Output is correct
23 Correct 4162 ms 112108 KB Output is correct
24 Execution timed out 8039 ms 114420 KB Time limit exceeded
25 Halted 0 ms 0 KB -