oj.uz

Submission #853772

# Submission time Handle Problem Language Result Execution time Memory
853772 2023-09-25T07:58:31 Z anha3k25cvp Factories (JOI14_factories) C++14
33 / 100
 8000 ms 129260 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;
    ll res = inf;
    if (S < T) {
        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);
            }
        }
        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]);
            }
        }
    }
    else {
        for (int i = 0; i < T; i ++) {
            int u = Y[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);
            }
        }
        for (int i = 0; i < S; i ++) {
            int u = X[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 16728 KB Output is correct
2 Correct 336 ms 21752 KB Output is correct
3 Correct 722 ms 21708 KB Output is correct
4 Correct 605 ms 21844 KB Output is correct
5 Correct 627 ms 22236 KB Output is correct
6 Correct 151 ms 21700 KB Output is correct
7 Correct 653 ms 21584 KB Output is correct
8 Correct 655 ms 21692 KB Output is correct
9 Correct 612 ms 22216 KB Output is correct
10 Correct 150 ms 21948 KB Output is correct
11 Correct 653 ms 21584 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16728 KB Output is correct
2 Correct 2383 ms 104900 KB Output is correct
3 Correct 5375 ms 107796 KB Output is correct
4 Correct 516 ms 105584 KB Output is correct
5 Correct 6740 ms 129260 KB Output is correct
6 Correct 5806 ms 107888 KB Output is correct
7 Correct 2719 ms 37912 KB Output is correct
8 Correct 243 ms 37572 KB Output is correct
9 Correct 2036 ms 40536 KB Output is correct
10 Correct 2738 ms 38204 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16728 KB Output is correct
2 Correct 336 ms 21752 KB Output is correct
3 Correct 722 ms 21708 KB Output is correct
4 Correct 605 ms 21844 KB Output is correct
5 Correct 627 ms 22236 KB Output is correct
6 Correct 151 ms 21700 KB Output is correct
7 Correct 653 ms 21584 KB Output is correct
8 Correct 655 ms 21692 KB Output is correct
9 Correct 612 ms 22216 KB Output is correct
10 Correct 150 ms 21948 KB Output is correct
11 Correct 653 ms 21584 KB Output is correct
12 Correct 3 ms 16728 KB Output is correct
13 Correct 2383 ms 104900 KB Output is correct
14 Correct 5375 ms 107796 KB Output is correct
15 Correct 516 ms 105584 KB Output is correct
16 Correct 6740 ms 129260 KB Output is correct
17 Correct 5806 ms 107888 KB Output is correct
18 Correct 2719 ms 37912 KB Output is correct
19 Correct 243 ms 37572 KB Output is correct
20 Correct 2036 ms 40536 KB Output is correct
21 Correct 2738 ms 38204 KB Output is correct
22 Correct 3626 ms 107780 KB Output is correct
23 Correct 3736 ms 105340 KB Output is correct
24 Execution timed out 8026 ms 114088 KB Time limit exceeded
25 Halted 0 ms 0 KB -