oj.uz

Submission #422381

# Submission time Handle Problem Language Result Execution time Memory
422381 2021-06-10T05:26:27 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 282452 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 22, M = 2 * N + 5;
std::vector<std::pair<int, i64>> e[N];
std::pair<int, int> st[M][K + 1];
int lg[M + 1];
int n, P[N];
i64 D[N];
int timer = 0;
std::pair<int, int> pos[M];
void dfs(int u, int p, i64 d = 0, int d1 = 0){
    P[u] = timer;
    pos[timer++] = {d1, u};
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs(v, u, d + w, d1 + 1);
            pos[timer++] = {d1, u};
        }
    }
}
inline std::pair<int, int> range(int L, int R) {
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    auto minimum = std::min(st[L][j], st[R - (1 << j) + 1][j]);
    return minimum;
}
inline int lca(int u, int v) {
    return range(P[u], P[v]).second;
}
i64 dist(int u, int v) {
    return D[u] + D[v] - 2 * D[lca(u, v)];
}
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[i][0] = pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= M; i++)
            st[i][j] = std::min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
}
i64 dp[N];
void dfs2(int u, int p) {
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs2(v, u);
            dp[u] = std::min(dp[u], dp[v] + w);
        }
    }
}
void dfs3(int u, int p) {
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dp[v] = std::min(dp[v], dp[u] + w);
            dfs3(v, u);
        }
    }
}
long long Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 500) {
        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;
    }
    dfs2(0, 0);
    dfs3(0, 0);
    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 377 ms 196412 KB Output is correct
2 Correct 1148 ms 208420 KB Output is correct
3 Correct 5141 ms 204484 KB Output is correct
4 Correct 896 ms 208476 KB Output is correct
5 Correct 1191 ms 208736 KB Output is correct
6 Correct 908 ms 208436 KB Output is correct
7 Correct 4434 ms 204620 KB Output is correct
8 Correct 907 ms 208384 KB Output is correct
9 Correct 1188 ms 208836 KB Output is correct
10 Correct 912 ms 208392 KB Output is correct
11 Correct 4593 ms 204548 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 196152 KB Output is correct
2 Correct 1389 ms 248260 KB Output is correct
3 Correct 1511 ms 251996 KB Output is correct
4 Correct 1197 ms 245752 KB Output is correct
5 Correct 1455 ms 282452 KB Output is correct
6 Correct 1467 ms 253524 KB Output is correct
7 Correct 1678 ms 215288 KB Output is correct
8 Correct 1266 ms 214960 KB Output is correct
9 Correct 1361 ms 219784 KB Output is correct
10 Correct 1311 ms 216416 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 196412 KB Output is correct
2 Correct 1148 ms 208420 KB Output is correct
3 Correct 5141 ms 204484 KB Output is correct
4 Correct 896 ms 208476 KB Output is correct
5 Correct 1191 ms 208736 KB Output is correct
6 Correct 908 ms 208436 KB Output is correct
7 Correct 4434 ms 204620 KB Output is correct
8 Correct 907 ms 208384 KB Output is correct
9 Correct 1188 ms 208836 KB Output is correct
10 Correct 912 ms 208392 KB Output is correct
11 Correct 4593 ms 204548 KB Output is correct
12 Correct 392 ms 196152 KB Output is correct
13 Correct 1389 ms 248260 KB Output is correct
14 Correct 1511 ms 251996 KB Output is correct
15 Correct 1197 ms 245752 KB Output is correct
16 Correct 1455 ms 282452 KB Output is correct
17 Correct 1467 ms 253524 KB Output is correct
18 Correct 1678 ms 215288 KB Output is correct
19 Correct 1266 ms 214960 KB Output is correct
20 Correct 1361 ms 219784 KB Output is correct
21 Correct 1311 ms 216416 KB Output is correct
22 Execution timed out 8103 ms 253448 KB Time limit exceeded
23 Halted 0 ms 0 KB -