oj.uz

Submission #422398

# Submission time Handle Problem Language Result Execution time Memory
422398 2021-06-10T05:43:52 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 282828 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], n, P[N], timer;
i64 D[N];
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 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.second;
}
inline i64 dist(int u, int v) {
    return D[u] + D[v] - 2 * D[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 <= 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;
    }
    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 394 ms 196292 KB Output is correct
2 Correct 1732 ms 208324 KB Output is correct
3 Correct 4498 ms 204468 KB Output is correct
4 Correct 1042 ms 208408 KB Output is correct
5 Correct 1517 ms 208716 KB Output is correct
6 Correct 1381 ms 208356 KB Output is correct
7 Correct 4147 ms 204552 KB Output is correct
8 Correct 1008 ms 209288 KB Output is correct
9 Correct 1562 ms 209616 KB Output is correct
10 Correct 1414 ms 209276 KB Output is correct
11 Correct 4305 ms 205372 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 196292 KB Output is correct
2 Correct 1432 ms 248236 KB Output is correct
3 Correct 1519 ms 252280 KB Output is correct
4 Correct 1204 ms 246184 KB Output is correct
5 Correct 1423 ms 282828 KB Output is correct
6 Correct 1406 ms 253536 KB Output is correct
7 Correct 1532 ms 216476 KB Output is correct
8 Correct 1164 ms 216020 KB Output is correct
9 Correct 1185 ms 221112 KB Output is correct
10 Correct 1226 ms 217632 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 196292 KB Output is correct
2 Correct 1732 ms 208324 KB Output is correct
3 Correct 4498 ms 204468 KB Output is correct
4 Correct 1042 ms 208408 KB Output is correct
5 Correct 1517 ms 208716 KB Output is correct
6 Correct 1381 ms 208356 KB Output is correct
7 Correct 4147 ms 204552 KB Output is correct
8 Correct 1008 ms 209288 KB Output is correct
9 Correct 1562 ms 209616 KB Output is correct
10 Correct 1414 ms 209276 KB Output is correct
11 Correct 4305 ms 205372 KB Output is correct
12 Correct 374 ms 196292 KB Output is correct
13 Correct 1432 ms 248236 KB Output is correct
14 Correct 1519 ms 252280 KB Output is correct
15 Correct 1204 ms 246184 KB Output is correct
16 Correct 1423 ms 282828 KB Output is correct
17 Correct 1406 ms 253536 KB Output is correct
18 Correct 1532 ms 216476 KB Output is correct
19 Correct 1164 ms 216020 KB Output is correct
20 Correct 1185 ms 221112 KB Output is correct
21 Correct 1226 ms 217632 KB Output is correct
22 Execution timed out 8082 ms 253736 KB Time limit exceeded
23 Halted 0 ms 0 KB -