oj.uz

Submission #422481

# Submission time Handle Problem Language Result Execution time Memory
422481 2021-06-10T07:20:02 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 275260 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 <= 1850) {
        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 121 ms 200260 KB Output is correct
2 Correct 2920 ms 213176 KB Output is correct
3 Correct 2133 ms 208488 KB Output is correct
4 Correct 762 ms 213348 KB Output is correct
5 Correct 2815 ms 213544 KB Output is correct
6 Correct 2881 ms 213380 KB Output is correct
7 Correct 2131 ms 208688 KB Output is correct
8 Correct 714 ms 213248 KB Output is correct
9 Correct 2792 ms 213364 KB Output is correct
10 Correct 2872 ms 213336 KB Output is correct
11 Correct 2149 ms 208588 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 200192 KB Output is correct
2 Correct 1081 ms 251052 KB Output is correct
3 Correct 1087 ms 252584 KB Output is correct
4 Correct 848 ms 251876 KB Output is correct
5 Correct 1094 ms 275260 KB Output is correct
6 Correct 1064 ms 253988 KB Output is correct
7 Correct 1061 ms 218564 KB Output is correct
8 Correct 761 ms 219468 KB Output is correct
9 Correct 739 ms 222104 KB Output is correct
10 Correct 774 ms 219784 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 200260 KB Output is correct
2 Correct 2920 ms 213176 KB Output is correct
3 Correct 2133 ms 208488 KB Output is correct
4 Correct 762 ms 213348 KB Output is correct
5 Correct 2815 ms 213544 KB Output is correct
6 Correct 2881 ms 213380 KB Output is correct
7 Correct 2131 ms 208688 KB Output is correct
8 Correct 714 ms 213248 KB Output is correct
9 Correct 2792 ms 213364 KB Output is correct
10 Correct 2872 ms 213336 KB Output is correct
11 Correct 2149 ms 208588 KB Output is correct
12 Correct 109 ms 200192 KB Output is correct
13 Correct 1081 ms 251052 KB Output is correct
14 Correct 1087 ms 252584 KB Output is correct
15 Correct 848 ms 251876 KB Output is correct
16 Correct 1094 ms 275260 KB Output is correct
17 Correct 1064 ms 253988 KB Output is correct
18 Correct 1061 ms 218564 KB Output is correct
19 Correct 761 ms 219468 KB Output is correct
20 Correct 739 ms 222104 KB Output is correct
21 Correct 774 ms 219784 KB Output is correct
22 Correct 1967 ms 257348 KB Output is correct
23 Correct 1485 ms 259676 KB Output is correct
24 Correct 1948 ms 259340 KB Output is correct
25 Correct 1759 ms 262760 KB Output is correct
26 Execution timed out 8026 ms 259336 KB Time limit exceeded
27 Halted 0 ms 0 KB -