oj.uz

Submission #422408

# Submission time Handle Problem Language Result Execution time Memory
422408 2021-06-10T05:54:29 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 260108 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 20, M = 2 * N + 5;
std::vector<std::pair<int, i64>> e[N];
i64 st[M][K + 1];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
void dfs(int u, int p, i64 d = 0){
    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 range(int L, int R) {
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    return std::min(st[L][j], st[R - (1 << j) + 1][j]);
}
inline i64 dist(int u, int v) {
    return D[u] + D[v] - 2 * range(P[u], P[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]);
}
i64 dp[N];
void dfs2(int u, int p) {
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs2(v, u);
            dp[u] = std::min(dp[u], dp[v] + w);
        }
    }
}
void dfs3(int u, int p) {
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dp[v] = std::min(dp[v], dp[u] + w);
            dfs3(v, u);
        }
    }
}
long long Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 2000) {
        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;
    }
    dfs2(0, 0);
    dfs3(0, 0);
    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 318 ms 180668 KB Output is correct
2 Correct 4521 ms 192656 KB Output is correct
3 Correct 2585 ms 188904 KB Output is correct
4 Correct 1177 ms 192724 KB Output is correct
5 Correct 4334 ms 193128 KB Output is correct
6 Correct 4430 ms 192696 KB Output is correct
7 Correct 2775 ms 188820 KB Output is correct
8 Correct 1103 ms 192708 KB Output is correct
9 Correct 4355 ms 193116 KB Output is correct
10 Correct 4388 ms 192768 KB Output is correct
11 Correct 2660 ms 188884 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 180420 KB Output is correct
2 Correct 1243 ms 232504 KB Output is correct
3 Correct 1406 ms 235472 KB Output is correct
4 Correct 1102 ms 230168 KB Output is correct
5 Correct 1308 ms 260108 KB Output is correct
6 Correct 1279 ms 236744 KB Output is correct
7 Correct 1361 ms 199496 KB Output is correct
8 Correct 1113 ms 199216 KB Output is correct
9 Correct 1122 ms 203440 KB Output is correct
10 Correct 1073 ms 200740 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 180668 KB Output is correct
2 Correct 4521 ms 192656 KB Output is correct
3 Correct 2585 ms 188904 KB Output is correct
4 Correct 1177 ms 192724 KB Output is correct
5 Correct 4334 ms 193128 KB Output is correct
6 Correct 4430 ms 192696 KB Output is correct
7 Correct 2775 ms 188820 KB Output is correct
8 Correct 1103 ms 192708 KB Output is correct
9 Correct 4355 ms 193116 KB Output is correct
10 Correct 4388 ms 192768 KB Output is correct
11 Correct 2660 ms 188884 KB Output is correct
12 Correct 326 ms 180420 KB Output is correct
13 Correct 1243 ms 232504 KB Output is correct
14 Correct 1406 ms 235472 KB Output is correct
15 Correct 1102 ms 230168 KB Output is correct
16 Correct 1308 ms 260108 KB Output is correct
17 Correct 1279 ms 236744 KB Output is correct
18 Correct 1361 ms 199496 KB Output is correct
19 Correct 1113 ms 199216 KB Output is correct
20 Correct 1122 ms 203440 KB Output is correct
21 Correct 1073 ms 200740 KB Output is correct
22 Execution timed out 8042 ms 237736 KB Time limit exceeded
23 Halted 0 ms 0 KB -