oj.uz

Submission #422373

# Submission time Handle Problem Language Result Execution time Memory
422373 2021-06-10T05:03:49 Z tengiz05 Factories (JOI14_factories) C++17
15 / 100
 4685 ms 296300 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 20;
std::vector<std::pair<int, i64>> e[N];
std::pair<int, int> st[N][K + 1];
int lg[N + 1];
int n, P[N];
i64 D[N];
int timer = 0;
std::pair<int, int> pos[2 * N];
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 <= N; 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 < N; i++)
        st[i][0] = pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= N; 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 210 ms 96492 KB Output is correct
2 Correct 1763 ms 104768 KB Output is correct
3 Correct 4685 ms 104680 KB Output is correct
4 Correct 897 ms 104896 KB Output is correct
5 Correct 1420 ms 105244 KB Output is correct
6 Correct 1516 ms 104884 KB Output is correct
7 Correct 4445 ms 104796 KB Output is correct
8 Correct 800 ms 104864 KB Output is correct
9 Correct 1440 ms 105244 KB Output is correct
10 Correct 1527 ms 104872 KB Output is correct
11 Correct 4568 ms 104792 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 96452 KB Output is correct
2 Runtime error 1012 ms 296300 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 210 ms 96492 KB Output is correct
2 Correct 1763 ms 104768 KB Output is correct
3 Correct 4685 ms 104680 KB Output is correct
4 Correct 897 ms 104896 KB Output is correct
5 Correct 1420 ms 105244 KB Output is correct
6 Correct 1516 ms 104884 KB Output is correct
7 Correct 4445 ms 104796 KB Output is correct
8 Correct 800 ms 104864 KB Output is correct
9 Correct 1440 ms 105244 KB Output is correct
10 Correct 1527 ms 104872 KB Output is correct
11 Correct 4568 ms 104792 KB Output is correct
12 Correct 184 ms 96452 KB Output is correct
13 Runtime error 1012 ms 296300 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -