oj.uz

Submission #422374

# Submission time Handle Problem Language Result Execution time Memory
422374 2021-06-10T05:05:51 Z tengiz05 Factories (JOI14_factories) C++17
15 / 100
 5199 ms 464224 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 20, M = N * 2;
std::vector<std::pair<int, i64>> e[N];
std::pair<int, int> st[M][K + 1];
int lg[M + 1];
int n, P[N];
i64 D[N];
int timer = 0;
std::pair<int, int> pos[M];
void dfs(int u, int p, i64 d = 0, int d1 = 0){
    P[u] = timer;
    pos[timer++] = {d1, u};
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs(v, u, d + w, d1 + 1);
        }
        pos[timer++] = {d1, u};
    }
}
inline std::pair<int, int> range(int L, int R) {
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    auto minimum = std::min(st[L][j], st[R - (1 << j) + 1][j]);
    return minimum;
}
inline int lca(int u, int v) {
    return range(P[u], P[v]).second;
}
i64 dist(int u, int v) {
    return D[u] + D[v] - 2 * D[lca(u, v)];
}
void Init(int n, int A[], int B[], int D[]) {
    lg[1] = 0;
    for (int i = 2; i <= M; i++)
        lg[i] = lg[i / 2] + 1;
    ::n = n;
    for (int i = 0; i < n - 1; i++) {
        e[A[i]].emplace_back(B[i], D[i]);
        e[B[i]].emplace_back(A[i], D[i]);
    }
    dfs(0, 0);
    for (int i = 0; i < M; i++)
        st[i][0] = pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= M; i++)
            st[i][j] = std::min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
}
long long Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 1000) {
        i64 ans = 1e16;
        for (int i = 0; i < S; i++) {
            for (int j = 0; j < T; j++) {
                ans = std::min(ans, dist(X[i], Y[j]));
            }
        }
        return ans;
    }
    std::priority_queue<std::pair<i64, int>, std::vector<std::pair<i64, int>>, std::greater<std::pair<i64, int>>> q;
    std::vector<i64> dist(n, 1e16);
    for (int i = 0; i < S; i++) {
        q.emplace(0, X[i]);
        dist[X[i]] = 0;
    }
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u]) {
            continue;
        }
        for (auto [v, w] : e[u]) {
            if (dist[v] > d + w) {
                dist[v] = d + w;
                q.emplace(dist[v], v);
            }
        }
    }
    i64 ans =  1e16;
    for (int i = 0; i < T; i++) {
        ans = std::min(ans, dist[Y[i]]);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 180888 KB Output is correct
2 Correct 1969 ms 189528 KB Output is correct
3 Correct 5199 ms 189032 KB Output is correct
4 Correct 1201 ms 189120 KB Output is correct
5 Correct 1609 ms 189336 KB Output is correct
6 Correct 1721 ms 189284 KB Output is correct
7 Correct 5026 ms 188852 KB Output is correct
8 Correct 987 ms 189052 KB Output is correct
9 Correct 1622 ms 189412 KB Output is correct
10 Correct 1620 ms 189132 KB Output is correct
11 Correct 4595 ms 189040 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 180540 KB Output is correct
2 Runtime error 1275 ms 464224 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 180888 KB Output is correct
2 Correct 1969 ms 189528 KB Output is correct
3 Correct 5199 ms 189032 KB Output is correct
4 Correct 1201 ms 189120 KB Output is correct
5 Correct 1609 ms 189336 KB Output is correct
6 Correct 1721 ms 189284 KB Output is correct
7 Correct 5026 ms 188852 KB Output is correct
8 Correct 987 ms 189052 KB Output is correct
9 Correct 1622 ms 189412 KB Output is correct
10 Correct 1620 ms 189132 KB Output is correct
11 Correct 4595 ms 189040 KB Output is correct
12 Correct 362 ms 180540 KB Output is correct
13 Runtime error 1275 ms 464224 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -