oj.uz

Submission #422425

# Submission time Handle Problem Language Result Execution time Memory
422425 2021-06-10T06:28:41 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 4003 ms 264452 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 20, M = 2 * N + 5;
std::vector<std::pair<int, i64>> e[N];
i64 st[M][K + 1];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
std::vector<int> order;
int par[N];
void dfs(int u, int p, i64 d = 0){
    order.push_back(u);
    par[u] = p;
    P[u] = timer;
    pos[timer++] = d;
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs(v, u, d + w);
            pos[timer++] = d;
        }
    }
}
inline i64 range(int L, int R) {
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    return std::min(st[L][j], st[R - (1 << j) + 1][j]);
}
inline i64 dist(int u, int v) {
    return D[u] + D[v] - 2 * range(P[u], P[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 <= 1500) {
        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--) {
        for (auto [v, w] : e[i]) {
            if (v != par[i]) {
                dp[i] = std::min(dp[i], dp[v] + w);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (auto [v, w] : e[i]) {
            if (v != par[i]) {
                dp[v] = std::min(dp[v], dp[i] + w);
            }
        }
    }
    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 326 ms 180820 KB Output is correct
2 Correct 2124 ms 193412 KB Output is correct
3 Correct 2682 ms 191820 KB Output is correct
4 Correct 950 ms 195876 KB Output is correct
5 Correct 2054 ms 196072 KB Output is correct
6 Correct 2029 ms 195692 KB Output is correct
7 Correct 2615 ms 191832 KB Output is correct
8 Correct 905 ms 195600 KB Output is correct
9 Correct 2064 ms 195904 KB Output is correct
10 Correct 2009 ms 195568 KB Output is correct
11 Correct 2648 ms 191704 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 180532 KB Output is correct
2 Correct 1323 ms 236680 KB Output is correct
3 Correct 1390 ms 239788 KB Output is correct
4 Correct 1124 ms 236512 KB Output is correct
5 Correct 1377 ms 264452 KB Output is correct
6 Correct 1370 ms 241128 KB Output is correct
7 Correct 1411 ms 205644 KB Output is correct
8 Correct 1112 ms 205860 KB Output is correct
9 Correct 1102 ms 209472 KB Output is correct
10 Correct 1118 ms 206820 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 180820 KB Output is correct
2 Correct 2124 ms 193412 KB Output is correct
3 Correct 2682 ms 191820 KB Output is correct
4 Correct 950 ms 195876 KB Output is correct
5 Correct 2054 ms 196072 KB Output is correct
6 Correct 2029 ms 195692 KB Output is correct
7 Correct 2615 ms 191832 KB Output is correct
8 Correct 905 ms 195600 KB Output is correct
9 Correct 2064 ms 195904 KB Output is correct
10 Correct 2009 ms 195568 KB Output is correct
11 Correct 2648 ms 191704 KB Output is correct
12 Correct 313 ms 180532 KB Output is correct
13 Correct 1323 ms 236680 KB Output is correct
14 Correct 1390 ms 239788 KB Output is correct
15 Correct 1124 ms 236512 KB Output is correct
16 Correct 1377 ms 264452 KB Output is correct
17 Correct 1370 ms 241128 KB Output is correct
18 Correct 1411 ms 205644 KB Output is correct
19 Correct 1112 ms 205860 KB Output is correct
20 Correct 1102 ms 209472 KB Output is correct
21 Correct 1118 ms 206820 KB Output is correct
22 Incorrect 4003 ms 242436 KB Output isn't correct
23 Halted 0 ms 0 KB -