oj.uz

Submission #422524

# Submission time Handle Problem Language Result Execution time Memory
422524 2021-06-10T07:57:23 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 275160 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 <= 5050) {
        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 126 ms 200388 KB Output is correct
2 Correct 6964 ms 208488 KB Output is correct
3 Correct 2215 ms 208704 KB Output is correct
4 Correct 2526 ms 208492 KB Output is correct
5 Correct 6828 ms 208672 KB Output is correct
6 Correct 7177 ms 208444 KB Output is correct
7 Correct 2114 ms 208696 KB Output is correct
8 Correct 2598 ms 208456 KB Output is correct
9 Correct 6799 ms 208668 KB Output is correct
10 Correct 7231 ms 208444 KB Output is correct
11 Correct 2131 ms 208712 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 200180 KB Output is correct
2 Correct 1047 ms 251096 KB Output is correct
3 Correct 1114 ms 252708 KB Output is correct
4 Correct 886 ms 251844 KB Output is correct
5 Correct 1081 ms 275160 KB Output is correct
6 Correct 1048 ms 254032 KB Output is correct
7 Correct 998 ms 218592 KB Output is correct
8 Correct 817 ms 219268 KB Output is correct
9 Correct 690 ms 222112 KB Output is correct
10 Correct 750 ms 219808 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 200388 KB Output is correct
2 Correct 6964 ms 208488 KB Output is correct
3 Correct 2215 ms 208704 KB Output is correct
4 Correct 2526 ms 208492 KB Output is correct
5 Correct 6828 ms 208672 KB Output is correct
6 Correct 7177 ms 208444 KB Output is correct
7 Correct 2114 ms 208696 KB Output is correct
8 Correct 2598 ms 208456 KB Output is correct
9 Correct 6799 ms 208668 KB Output is correct
10 Correct 7231 ms 208444 KB Output is correct
11 Correct 2131 ms 208712 KB Output is correct
12 Correct 111 ms 200180 KB Output is correct
13 Correct 1047 ms 251096 KB Output is correct
14 Correct 1114 ms 252708 KB Output is correct
15 Correct 886 ms 251844 KB Output is correct
16 Correct 1081 ms 275160 KB Output is correct
17 Correct 1048 ms 254032 KB Output is correct
18 Correct 998 ms 218592 KB Output is correct
19 Correct 817 ms 219268 KB Output is correct
20 Correct 690 ms 222112 KB Output is correct
21 Correct 750 ms 219808 KB Output is correct
22 Correct 1823 ms 257292 KB Output is correct
23 Correct 1525 ms 259684 KB Output is correct
24 Correct 1887 ms 259284 KB Output is correct
25 Correct 1977 ms 262752 KB Output is correct
26 Execution timed out 8086 ms 254588 KB Time limit exceeded
27 Halted 0 ms 0 KB -