oj.uz

Submission #422527

# Submission time Handle Problem Language Result Execution time Memory
422527 2021-06-10T08:00:42 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 239772 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 <= 10050) {
        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 102 ms 164608 KB Output is correct
2 Correct 6933 ms 172836 KB Output is correct
3 Correct 2103 ms 172816 KB Output is correct
4 Correct 2607 ms 172796 KB Output is correct
5 Correct 6812 ms 173028 KB Output is correct
6 Correct 6999 ms 172808 KB Output is correct
7 Correct 2078 ms 172940 KB Output is correct
8 Correct 2621 ms 173004 KB Output is correct
9 Correct 6882 ms 173028 KB Output is correct
10 Correct 6953 ms 172808 KB Output is correct
11 Correct 2183 ms 173004 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 164436 KB Output is correct
2 Correct 1035 ms 215512 KB Output is correct
3 Correct 1163 ms 216988 KB Output is correct
4 Correct 903 ms 216136 KB Output is correct
5 Correct 1038 ms 239772 KB Output is correct
6 Correct 1004 ms 218412 KB Output is correct
7 Correct 1016 ms 183092 KB Output is correct
8 Correct 770 ms 183788 KB Output is correct
9 Correct 673 ms 186648 KB Output is correct
10 Correct 767 ms 184152 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 164608 KB Output is correct
2 Correct 6933 ms 172836 KB Output is correct
3 Correct 2103 ms 172816 KB Output is correct
4 Correct 2607 ms 172796 KB Output is correct
5 Correct 6812 ms 173028 KB Output is correct
6 Correct 6999 ms 172808 KB Output is correct
7 Correct 2078 ms 172940 KB Output is correct
8 Correct 2621 ms 173004 KB Output is correct
9 Correct 6882 ms 173028 KB Output is correct
10 Correct 6953 ms 172808 KB Output is correct
11 Correct 2183 ms 173004 KB Output is correct
12 Correct 90 ms 164436 KB Output is correct
13 Correct 1035 ms 215512 KB Output is correct
14 Correct 1163 ms 216988 KB Output is correct
15 Correct 903 ms 216136 KB Output is correct
16 Correct 1038 ms 239772 KB Output is correct
17 Correct 1004 ms 218412 KB Output is correct
18 Correct 1016 ms 183092 KB Output is correct
19 Correct 770 ms 183788 KB Output is correct
20 Correct 673 ms 186648 KB Output is correct
21 Correct 767 ms 184152 KB Output is correct
22 Correct 1947 ms 220888 KB Output is correct
23 Correct 1554 ms 223140 KB Output is correct
24 Correct 2289 ms 222884 KB Output is correct
25 Correct 2094 ms 226212 KB Output is correct
26 Execution timed out 8032 ms 219056 KB Time limit exceeded
27 Halted 0 ms 0 KB -