oj.uz

Submission #422437

# Submission time Handle Problem Language Result Execution time Memory
422437 2021-06-10T06:42:06 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 248300 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 21, M = 2 * N + 5;
std::vector<std::pair<int, i64>> e[N];
i64 st[K + 1][M];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
std::vector<int> order;
int par[N];
void dfs(int u, int p, i64 d = 0){
    order.push_back(u);
    par[u] = p;
    P[u] = timer;
    pos[timer++] = d;
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs(v, u, d + w);
            pos[timer++] = d;
        }
    }
}
inline i64 dist(int u, int v) {
    int L = P[u], R = P[v];
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    return D[u] + D[v] - 2 * std::min(st[j][L], st[j][R - (1 << j) + 1]);
}
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[0][i] = pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= M; i++)
            st[j][i] = std::min(st[j-1][i], st[j - 1][i + (1 << (j - 1))]);
}
i64 dp[N];
long long Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 1200) {
        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;
    }
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < S; i++) {
        dp[X[i]] = 0;
    }
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        for (auto [v, w] : e[u]) {
            if (v != par[u]) {
                dp[u] = std::min(dp[u], dp[v] + w);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (auto [v, w] : e[u]) {
            if (v != par[u]) {
                dp[v] = std::min(dp[v], dp[u] + w);
            }
        }
    }
    i64 ans =  1e16;
    for (int i = 0; i < T; i++) {
        ans = std::min(ans, dp[Y[i]]);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 164648 KB Output is correct
2 Correct 1133 ms 176876 KB Output is correct
3 Correct 2141 ms 173016 KB Output is correct
4 Correct 582 ms 176828 KB Output is correct
5 Correct 1046 ms 177088 KB Output is correct
6 Correct 992 ms 176788 KB Output is correct
7 Correct 2233 ms 173124 KB Output is correct
8 Correct 554 ms 176908 KB Output is correct
9 Correct 1030 ms 177104 KB Output is correct
10 Correct 1089 ms 176836 KB Output is correct
11 Correct 2169 ms 173008 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 164548 KB Output is correct
2 Correct 1042 ms 220616 KB Output is correct
3 Correct 1122 ms 223496 KB Output is correct
4 Correct 867 ms 220244 KB Output is correct
5 Correct 1067 ms 248300 KB Output is correct
6 Correct 1063 ms 224908 KB Output is correct
7 Correct 996 ms 184328 KB Output is correct
8 Correct 769 ms 184496 KB Output is correct
9 Correct 688 ms 188412 KB Output is correct
10 Correct 749 ms 185644 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 164648 KB Output is correct
2 Correct 1133 ms 176876 KB Output is correct
3 Correct 2141 ms 173016 KB Output is correct
4 Correct 582 ms 176828 KB Output is correct
5 Correct 1046 ms 177088 KB Output is correct
6 Correct 992 ms 176788 KB Output is correct
7 Correct 2233 ms 173124 KB Output is correct
8 Correct 554 ms 176908 KB Output is correct
9 Correct 1030 ms 177104 KB Output is correct
10 Correct 1089 ms 176836 KB Output is correct
11 Correct 2169 ms 173008 KB Output is correct
12 Correct 91 ms 164548 KB Output is correct
13 Correct 1042 ms 220616 KB Output is correct
14 Correct 1122 ms 223496 KB Output is correct
15 Correct 867 ms 220244 KB Output is correct
16 Correct 1067 ms 248300 KB Output is correct
17 Correct 1063 ms 224908 KB Output is correct
18 Correct 996 ms 184328 KB Output is correct
19 Correct 769 ms 184496 KB Output is correct
20 Correct 688 ms 188412 KB Output is correct
21 Correct 749 ms 185644 KB Output is correct
22 Correct 5895 ms 226004 KB Output is correct
23 Correct 3188 ms 228360 KB Output is correct
24 Correct 6082 ms 229504 KB Output is correct
25 Correct 5385 ms 232804 KB Output is correct
26 Execution timed out 8090 ms 229376 KB Time limit exceeded
27 Halted 0 ms 0 KB -