oj.uz

Submission #422513

# Submission time Handle Problem Language Result Execution time Memory
422513 2021-06-10T07:48:00 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 275228 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 600000, K = 22, M = 2 * N + 1;
std::vector<std::pair<int, int>> e[N];
i64 st[K + 1][M];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
int order[N], timeStamp;
int par[N];
int dpar[N];
void dfs(int u, int p, i64 d = 0){
    order[timeStamp++] = u;
    par[u] = p;
    P[u] = timer;
    pos[timer++] = d;
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dpar[v] = w;
            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] - 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] = 2 * 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];
i64 Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 3050) {
        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];
        dp[par[u]] = std::min(dp[par[u]], dp[u] + dpar[u]);
    }
    for (int i = 0; i < n; i++) {
        int u = order[i];
        dp[u] = std::min(dp[u], dp[par[u]] + dpar[u]);
    }
    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 128 ms 200512 KB Output is correct
2 Correct 6793 ms 209604 KB Output is correct
3 Correct 2132 ms 209964 KB Output is correct
4 Correct 1355 ms 214668 KB Output is correct
5 Correct 6819 ms 210316 KB Output is correct
6 Correct 7044 ms 209980 KB Output is correct
7 Correct 2167 ms 210124 KB Output is correct
8 Correct 1632 ms 214540 KB Output is correct
9 Correct 6893 ms 210208 KB Output is correct
10 Correct 7162 ms 210024 KB Output is correct
11 Correct 2137 ms 209996 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 200108 KB Output is correct
2 Correct 1039 ms 251412 KB Output is correct
3 Correct 1114 ms 253404 KB Output is correct
4 Correct 863 ms 251832 KB Output is correct
5 Correct 1121 ms 275228 KB Output is correct
6 Correct 1088 ms 253980 KB Output is correct
7 Correct 986 ms 218556 KB Output is correct
8 Correct 747 ms 219260 KB Output is correct
9 Correct 719 ms 222080 KB Output is correct
10 Correct 785 ms 219832 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 200512 KB Output is correct
2 Correct 6793 ms 209604 KB Output is correct
3 Correct 2132 ms 209964 KB Output is correct
4 Correct 1355 ms 214668 KB Output is correct
5 Correct 6819 ms 210316 KB Output is correct
6 Correct 7044 ms 209980 KB Output is correct
7 Correct 2167 ms 210124 KB Output is correct
8 Correct 1632 ms 214540 KB Output is correct
9 Correct 6893 ms 210208 KB Output is correct
10 Correct 7162 ms 210024 KB Output is correct
11 Correct 2137 ms 209996 KB Output is correct
12 Correct 110 ms 200108 KB Output is correct
13 Correct 1039 ms 251412 KB Output is correct
14 Correct 1114 ms 253404 KB Output is correct
15 Correct 863 ms 251832 KB Output is correct
16 Correct 1121 ms 275228 KB Output is correct
17 Correct 1088 ms 253980 KB Output is correct
18 Correct 986 ms 218556 KB Output is correct
19 Correct 747 ms 219260 KB Output is correct
20 Correct 719 ms 222080 KB Output is correct
21 Correct 785 ms 219832 KB Output is correct
22 Correct 1826 ms 257348 KB Output is correct
23 Correct 1551 ms 259616 KB Output is correct
24 Correct 1827 ms 259252 KB Output is correct
25 Correct 1945 ms 262592 KB Output is correct
26 Execution timed out 8095 ms 254680 KB Time limit exceeded
27 Halted 0 ms 0 KB -