oj.uz

Submission #730570

# Submission time Handle Problem Language Result Execution time Memory
730570 2023-04-26T06:01:16 Z t6twotwo Factories (JOI14_factories) C++17
0 / 100
 8000 ms 131120 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int N, lg;
vector<int> p, dep;
vector<int64_t> dis;
vector<vector<int>> par;
vector<vector<pair<int, int>>> adj;
void Init(int n, int A[], int B[], int D[]) {
    N = n;
    p.resize(N);
    dis.resize(N);
    dep.resize(N);
    adj.resize(N);
    lg = __lg(N);
    par = vector(N, vector<int>(lg + 1, -1));
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    auto dfs = [&](auto dfs, int x, int p) -> void {
        for (int i = 0; i < lg && par[x][i] != -1; i++) {
            par[x][i + 1] = par[par[x][i]][i];
        }
        for (auto [y, z] : adj[x]) {
            if (y == p) {
                continue;
            }
            dep[y] = dep[x] + 1;
            dis[y] = dis[x] + z;
            par[y][0] = x;
            dfs(dfs, y, x);
        }
    };
    dfs(dfs, 0, -1);
    vector<bool> vis(N);
    vector<int> sz(N);
    auto init = [&](auto init, int x, int p) -> void {
        sz[x] = 1;
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y]) {
                continue;
            }
            dfs(dfs, y, x);
            sz[x] += sz[y];
        }
    };
    auto find = [&](auto find, int x, int p, int s) -> int {
        for (auto [y, _] : adj[x]) {
            if (y == p || vis[y] || sz[y] * 2 <= s) {
                continue;
            }
            return find(find, y, x, s);
        }
        return x;
    };
    auto cd = [&](auto cd, int x) -> int {
        init(init, x, -1);
        x = find(find, x, -1, sz[x]);
        vis[x] = 1;
        for (auto [y, _] : adj[x]) {
            if (vis[y]) {
                continue;
            }
            p[cd(cd, y)] = x;
        }
        return x;
    };
    p[cd(cd, 0)] = -1;
}
void lift(int &x, int d) {
    if (d < 0) {
        return;
    }
    for (int i = 0; i <= lg; i++) {
        if (d >> i & 1) {
            x = par[x][i];
        }
    }
}
int lca(int x, int y) {
    lift(x, dep[x] - dep[y]);
    lift(y, dep[y] - dep[x]);
    if (x == y) {
        return x;
    }
    for (int i = lg; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
int64_t dist(int x, int y) {
    return dis[x] + dis[y] - 2 * dis[lca(x, y)];
}
constexpr int64_t inf = 1E18;
long long Query(int S, int X[], int T, int Y[]) {
    vector<int64_t> best(N, inf);
    for (int i = 0; i < S; i++) {
        int x = X[i];
        while (x != -1) {
            best[x] = min(best[x], dist(x, X[i]));
            x = p[x];
        }
    }
    auto ans = inf;
    for (int i = 0; i < T; i++) {
        int x = Y[i];
        while (x != -1) {
            ans = min(ans, best[x] + dist(x, Y[i]));
            x = p[x];
        }
    }
    return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 852 KB Output is correct
2 Correct 780 ms 18716 KB Output is correct
3 Execution timed out 8016 ms 18796 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 852 KB Output is correct
2 Correct 780 ms 18716 KB Output is correct
3 Execution timed out 8016 ms 18796 KB Time limit exceeded
4 Halted 0 ms 0 KB -