oj.uz

Submission #422384

# Submission time Handle Problem Language Result Execution time Memory
422384 2021-06-10T05:29:42 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 282448 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 i64 dist(int u, int v) {
    return D[u] + D[v] - 2 * D[range(P[u], P[v]).second];
}
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 <= 1000) {
        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 410 ms 196320 KB Output is correct
2 Correct 1615 ms 208316 KB Output is correct
3 Correct 4373 ms 204680 KB Output is correct
4 Correct 1000 ms 208356 KB Output is correct
5 Correct 1391 ms 208812 KB Output is correct
6 Correct 1186 ms 208384 KB Output is correct
7 Correct 4029 ms 204604 KB Output is correct
8 Correct 861 ms 208444 KB Output is correct
9 Correct 1466 ms 208740 KB Output is correct
10 Correct 1206 ms 208452 KB Output is correct
11 Correct 4075 ms 204596 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 196176 KB Output is correct
2 Correct 1338 ms 248168 KB Output is correct
3 Correct 1422 ms 252104 KB Output is correct
4 Correct 1165 ms 245876 KB Output is correct
5 Correct 1356 ms 282448 KB Output is correct
6 Correct 1370 ms 253444 KB Output is correct
7 Correct 1520 ms 215320 KB Output is correct
8 Correct 1161 ms 214876 KB Output is correct
9 Correct 1170 ms 219976 KB Output is correct
10 Correct 1259 ms 216660 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 196320 KB Output is correct
2 Correct 1615 ms 208316 KB Output is correct
3 Correct 4373 ms 204680 KB Output is correct
4 Correct 1000 ms 208356 KB Output is correct
5 Correct 1391 ms 208812 KB Output is correct
6 Correct 1186 ms 208384 KB Output is correct
7 Correct 4029 ms 204604 KB Output is correct
8 Correct 861 ms 208444 KB Output is correct
9 Correct 1466 ms 208740 KB Output is correct
10 Correct 1206 ms 208452 KB Output is correct
11 Correct 4075 ms 204596 KB Output is correct
12 Correct 368 ms 196176 KB Output is correct
13 Correct 1338 ms 248168 KB Output is correct
14 Correct 1422 ms 252104 KB Output is correct
15 Correct 1165 ms 245876 KB Output is correct
16 Correct 1356 ms 282448 KB Output is correct
17 Correct 1370 ms 253444 KB Output is correct
18 Correct 1520 ms 215320 KB Output is correct
19 Correct 1161 ms 214876 KB Output is correct
20 Correct 1170 ms 219976 KB Output is correct
21 Correct 1259 ms 216660 KB Output is correct
22 Execution timed out 8034 ms 253436 KB Time limit exceeded
23 Halted 0 ms 0 KB -