oj.uz

Submission #422387

# Submission time Handle Problem Language Result Execution time Memory
422387 2021-06-10T05:35:47 Z tengiz05 Factories (JOI14_factories) C++17
18 / 100
 8000 ms 282436 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 <= 5000) {
        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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 196320 KB Output is correct
2 Execution timed out 8092 ms 204404 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 196148 KB Output is correct
2 Correct 1373 ms 248172 KB Output is correct
3 Correct 1481 ms 251984 KB Output is correct
4 Correct 1210 ms 246000 KB Output is correct
5 Correct 1348 ms 282436 KB Output is correct
6 Correct 1375 ms 253240 KB Output is correct
7 Correct 1588 ms 215412 KB Output is correct
8 Correct 1191 ms 214836 KB Output is correct
9 Correct 1159 ms 219904 KB Output is correct
10 Correct 1256 ms 216440 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 196320 KB Output is correct
2 Execution timed out 8092 ms 204404 KB Time limit exceeded
3 Halted 0 ms 0 KB -