oj.uz

Submission #422477

# Submission time Handle Problem Language Result Execution time Memory
422477 2021-06-10T07:10:32 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 275288 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 <= 1150) {
        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 135 ms 200268 KB Output is correct
2 Correct 1093 ms 213112 KB Output is correct
3 Correct 2219 ms 208492 KB Output is correct
4 Correct 633 ms 213136 KB Output is correct
5 Correct 997 ms 213356 KB Output is correct
6 Correct 1061 ms 213136 KB Output is correct
7 Correct 2155 ms 208532 KB Output is correct
8 Correct 543 ms 213148 KB Output is correct
9 Correct 983 ms 213364 KB Output is correct
10 Correct 969 ms 213116 KB Output is correct
11 Correct 2154 ms 208688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 200132 KB Output is correct
2 Correct 1132 ms 251188 KB Output is correct
3 Correct 1151 ms 252852 KB Output is correct
4 Correct 952 ms 252076 KB Output is correct
5 Correct 1102 ms 275288 KB Output is correct
6 Correct 1119 ms 254084 KB Output is correct
7 Correct 1149 ms 218684 KB Output is correct
8 Correct 762 ms 219468 KB Output is correct
9 Correct 684 ms 222052 KB Output is correct
10 Correct 767 ms 219804 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 200268 KB Output is correct
2 Correct 1093 ms 213112 KB Output is correct
3 Correct 2219 ms 208492 KB Output is correct
4 Correct 633 ms 213136 KB Output is correct
5 Correct 997 ms 213356 KB Output is correct
6 Correct 1061 ms 213136 KB Output is correct
7 Correct 2155 ms 208532 KB Output is correct
8 Correct 543 ms 213148 KB Output is correct
9 Correct 983 ms 213364 KB Output is correct
10 Correct 969 ms 213116 KB Output is correct
11 Correct 2154 ms 208688 KB Output is correct
12 Correct 115 ms 200132 KB Output is correct
13 Correct 1132 ms 251188 KB Output is correct
14 Correct 1151 ms 252852 KB Output is correct
15 Correct 952 ms 252076 KB Output is correct
16 Correct 1102 ms 275288 KB Output is correct
17 Correct 1119 ms 254084 KB Output is correct
18 Correct 1149 ms 218684 KB Output is correct
19 Correct 762 ms 219468 KB Output is correct
20 Correct 684 ms 222052 KB Output is correct
21 Correct 767 ms 219804 KB Output is correct
22 Correct 2153 ms 257224 KB Output is correct
23 Correct 1863 ms 259640 KB Output is correct
24 Correct 1990 ms 259340 KB Output is correct
25 Correct 1995 ms 262636 KB Output is correct
26 Execution timed out 8042 ms 259268 KB Time limit exceeded
27 Halted 0 ms 0 KB -