oj.uz

Submission #422508

# Submission time Handle Problem Language Result Execution time Memory
422508 2021-06-10T07:44:42 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 275572 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 <= 2250) {
        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 136 ms 200524 KB Output is correct
2 Correct 4786 ms 214540 KB Output is correct
3 Correct 2129 ms 210000 KB Output is correct
4 Correct 948 ms 214852 KB Output is correct
5 Correct 4752 ms 215204 KB Output is correct
6 Correct 4914 ms 215056 KB Output is correct
7 Correct 2145 ms 211152 KB Output is correct
8 Correct 1030 ms 215572 KB Output is correct
9 Correct 4795 ms 215156 KB Output is correct
10 Correct 4803 ms 214548 KB Output is correct
11 Correct 2252 ms 209992 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 200208 KB Output is correct
2 Correct 1058 ms 251436 KB Output is correct
3 Correct 1146 ms 253256 KB Output is correct
4 Correct 905 ms 252168 KB Output is correct
5 Correct 1206 ms 275572 KB Output is correct
6 Correct 1144 ms 254428 KB Output is correct
7 Correct 1014 ms 219692 KB Output is correct
8 Correct 815 ms 220472 KB Output is correct
9 Correct 706 ms 223316 KB Output is correct
10 Correct 804 ms 221076 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 200524 KB Output is correct
2 Correct 4786 ms 214540 KB Output is correct
3 Correct 2129 ms 210000 KB Output is correct
4 Correct 948 ms 214852 KB Output is correct
5 Correct 4752 ms 215204 KB Output is correct
6 Correct 4914 ms 215056 KB Output is correct
7 Correct 2145 ms 211152 KB Output is correct
8 Correct 1030 ms 215572 KB Output is correct
9 Correct 4795 ms 215156 KB Output is correct
10 Correct 4803 ms 214548 KB Output is correct
11 Correct 2252 ms 209992 KB Output is correct
12 Correct 124 ms 200208 KB Output is correct
13 Correct 1058 ms 251436 KB Output is correct
14 Correct 1146 ms 253256 KB Output is correct
15 Correct 905 ms 252168 KB Output is correct
16 Correct 1206 ms 275572 KB Output is correct
17 Correct 1144 ms 254428 KB Output is correct
18 Correct 1014 ms 219692 KB Output is correct
19 Correct 815 ms 220472 KB Output is correct
20 Correct 706 ms 223316 KB Output is correct
21 Correct 804 ms 221076 KB Output is correct
22 Correct 2167 ms 257676 KB Output is correct
23 Correct 1715 ms 260540 KB Output is correct
24 Correct 2171 ms 260036 KB Output is correct
25 Correct 2111 ms 263168 KB Output is correct
26 Execution timed out 8026 ms 255016 KB Time limit exceeded
27 Halted 0 ms 0 KB -