oj.uz

Submission #422528

# Submission time Handle Problem Language Result Execution time Memory
422528 2021-06-10T08:02:32 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 239520 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, 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 <= 14050) {
        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 104 ms 164728 KB Output is correct
2 Correct 6762 ms 172788 KB Output is correct
3 Correct 2116 ms 172824 KB Output is correct
4 Correct 2467 ms 172868 KB Output is correct
5 Correct 6800 ms 173068 KB Output is correct
6 Correct 7031 ms 172796 KB Output is correct
7 Correct 2084 ms 172800 KB Output is correct
8 Correct 2533 ms 172812 KB Output is correct
9 Correct 6752 ms 173028 KB Output is correct
10 Correct 6952 ms 172860 KB Output is correct
11 Correct 2115 ms 172988 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 164536 KB Output is correct
2 Correct 989 ms 215424 KB Output is correct
3 Correct 1099 ms 217072 KB Output is correct
4 Correct 866 ms 216144 KB Output is correct
5 Correct 1018 ms 239520 KB Output is correct
6 Correct 1000 ms 218244 KB Output is correct
7 Correct 992 ms 183088 KB Output is correct
8 Correct 720 ms 183736 KB Output is correct
9 Correct 713 ms 186568 KB Output is correct
10 Correct 736 ms 184176 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 164728 KB Output is correct
2 Correct 6762 ms 172788 KB Output is correct
3 Correct 2116 ms 172824 KB Output is correct
4 Correct 2467 ms 172868 KB Output is correct
5 Correct 6800 ms 173068 KB Output is correct
6 Correct 7031 ms 172796 KB Output is correct
7 Correct 2084 ms 172800 KB Output is correct
8 Correct 2533 ms 172812 KB Output is correct
9 Correct 6752 ms 173028 KB Output is correct
10 Correct 6952 ms 172860 KB Output is correct
11 Correct 2115 ms 172988 KB Output is correct
12 Correct 90 ms 164536 KB Output is correct
13 Correct 989 ms 215424 KB Output is correct
14 Correct 1099 ms 217072 KB Output is correct
15 Correct 866 ms 216144 KB Output is correct
16 Correct 1018 ms 239520 KB Output is correct
17 Correct 1000 ms 218244 KB Output is correct
18 Correct 992 ms 183088 KB Output is correct
19 Correct 720 ms 183736 KB Output is correct
20 Correct 713 ms 186568 KB Output is correct
21 Correct 736 ms 184176 KB Output is correct
22 Correct 4027 ms 220896 KB Output is correct
23 Correct 1800 ms 223340 KB Output is correct
24 Correct 3393 ms 222832 KB Output is correct
25 Correct 3729 ms 226324 KB Output is correct
26 Execution timed out 8069 ms 218992 KB Time limit exceeded
27 Halted 0 ms 0 KB -