oj.uz

Submission #422458

# Submission time Handle Problem Language Result Execution time Memory
422458 2021-06-10T06:58:47 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 273604 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 20, M = 2 * N + 1;
std::vector<std::pair<int, int>> e[N], e2[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) {
            e2[u].emplace_back(v, w);
            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] - 2 * 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] = 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 <= 1100) {
        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 115 ms 176452 KB Output is correct
2 Correct 928 ms 188576 KB Output is correct
3 Correct 2146 ms 184712 KB Output is correct
4 Correct 519 ms 188556 KB Output is correct
5 Correct 865 ms 188956 KB Output is correct
6 Correct 945 ms 188560 KB Output is correct
7 Correct 2168 ms 184688 KB Output is correct
8 Correct 499 ms 188628 KB Output is correct
9 Correct 825 ms 188964 KB Output is correct
10 Correct 916 ms 188628 KB Output is correct
11 Correct 2153 ms 184660 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 176212 KB Output is correct
2 Correct 1099 ms 236468 KB Output is correct
3 Correct 1163 ms 239988 KB Output is correct
4 Correct 890 ms 231884 KB Output is correct
5 Correct 1145 ms 273604 KB Output is correct
6 Correct 1137 ms 241256 KB Output is correct
7 Correct 1064 ms 196992 KB Output is correct
8 Correct 755 ms 196292 KB Output is correct
9 Correct 685 ms 202204 KB Output is correct
10 Correct 784 ms 198128 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 176452 KB Output is correct
2 Correct 928 ms 188576 KB Output is correct
3 Correct 2146 ms 184712 KB Output is correct
4 Correct 519 ms 188556 KB Output is correct
5 Correct 865 ms 188956 KB Output is correct
6 Correct 945 ms 188560 KB Output is correct
7 Correct 2168 ms 184688 KB Output is correct
8 Correct 499 ms 188628 KB Output is correct
9 Correct 825 ms 188964 KB Output is correct
10 Correct 916 ms 188628 KB Output is correct
11 Correct 2153 ms 184660 KB Output is correct
12 Correct 98 ms 176212 KB Output is correct
13 Correct 1099 ms 236468 KB Output is correct
14 Correct 1163 ms 239988 KB Output is correct
15 Correct 890 ms 231884 KB Output is correct
16 Correct 1145 ms 273604 KB Output is correct
17 Correct 1137 ms 241256 KB Output is correct
18 Correct 1064 ms 196992 KB Output is correct
19 Correct 755 ms 196292 KB Output is correct
20 Correct 685 ms 202204 KB Output is correct
21 Correct 784 ms 198128 KB Output is correct
22 Correct 1956 ms 241952 KB Output is correct
23 Correct 1561 ms 244284 KB Output is correct
24 Correct 1881 ms 245712 KB Output is correct
25 Correct 1942 ms 249184 KB Output is correct
26 Execution timed out 8055 ms 245832 KB Time limit exceeded
27 Halted 0 ms 0 KB -