oj.uz

Submission #422511

# Submission time Handle Problem Language Result Execution time Memory
422511 2021-06-10T07:46:55 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 275812 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 <= 1750) {
        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 127 ms 200260 KB Output is correct
2 Correct 2573 ms 213144 KB Output is correct
3 Correct 2162 ms 208556 KB Output is correct
4 Correct 739 ms 213136 KB Output is correct
5 Correct 2424 ms 213356 KB Output is correct
6 Correct 2484 ms 213132 KB Output is correct
7 Correct 2134 ms 208428 KB Output is correct
8 Correct 690 ms 213756 KB Output is correct
9 Correct 2473 ms 213996 KB Output is correct
10 Correct 2636 ms 213776 KB Output is correct
11 Correct 2312 ms 209116 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 200212 KB Output is correct
2 Correct 1088 ms 251228 KB Output is correct
3 Correct 1164 ms 253024 KB Output is correct
4 Correct 929 ms 252608 KB Output is correct
5 Correct 1155 ms 275812 KB Output is correct
6 Correct 1147 ms 254720 KB Output is correct
7 Correct 1087 ms 219616 KB Output is correct
8 Correct 897 ms 220212 KB Output is correct
9 Correct 671 ms 222996 KB Output is correct
10 Correct 820 ms 220752 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 200260 KB Output is correct
2 Correct 2573 ms 213144 KB Output is correct
3 Correct 2162 ms 208556 KB Output is correct
4 Correct 739 ms 213136 KB Output is correct
5 Correct 2424 ms 213356 KB Output is correct
6 Correct 2484 ms 213132 KB Output is correct
7 Correct 2134 ms 208428 KB Output is correct
8 Correct 690 ms 213756 KB Output is correct
9 Correct 2473 ms 213996 KB Output is correct
10 Correct 2636 ms 213776 KB Output is correct
11 Correct 2312 ms 209116 KB Output is correct
12 Correct 120 ms 200212 KB Output is correct
13 Correct 1088 ms 251228 KB Output is correct
14 Correct 1164 ms 253024 KB Output is correct
15 Correct 929 ms 252608 KB Output is correct
16 Correct 1155 ms 275812 KB Output is correct
17 Correct 1147 ms 254720 KB Output is correct
18 Correct 1087 ms 219616 KB Output is correct
19 Correct 897 ms 220212 KB Output is correct
20 Correct 671 ms 222996 KB Output is correct
21 Correct 820 ms 220752 KB Output is correct
22 Correct 2417 ms 257912 KB Output is correct
23 Correct 1806 ms 260604 KB Output is correct
24 Correct 2099 ms 260040 KB Output is correct
25 Correct 2171 ms 262744 KB Output is correct
26 Execution timed out 8032 ms 259312 KB Time limit exceeded
27 Halted 0 ms 0 KB -