oj.uz

Submission #422430

# Submission time Handle Problem Language Result Execution time Memory
422430 2021-06-10T06:33:02 Z tengiz05 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 264088 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];
long long Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 1200) {
        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--) {
        int u = order[i];
        for (auto [v, w] : e[u]) {
            if (v != par[u]) {
                dp[u] = std::min(dp[u], dp[v] + w);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (auto [v, w] : e[u]) {
            if (v != par[u]) {
                dp[v] = std::min(dp[v], dp[u] + 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 316 ms 180908 KB Output is correct
2 Correct 1516 ms 195004 KB Output is correct
3 Correct 2654 ms 190116 KB Output is correct
4 Correct 864 ms 193708 KB Output is correct
5 Correct 1337 ms 193412 KB Output is correct
6 Correct 1461 ms 192736 KB Output is correct
7 Correct 2646 ms 188988 KB Output is correct
8 Correct 871 ms 192860 KB Output is correct
9 Correct 1343 ms 193100 KB Output is correct
10 Correct 1355 ms 192772 KB Output is correct
11 Correct 2610 ms 188976 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 180536 KB Output is correct
2 Correct 1256 ms 236520 KB Output is correct
3 Correct 1445 ms 239616 KB Output is correct
4 Correct 1124 ms 236276 KB Output is correct
5 Correct 1296 ms 264088 KB Output is correct
6 Correct 1341 ms 240832 KB Output is correct
7 Correct 1344 ms 201172 KB Output is correct
8 Correct 1098 ms 201424 KB Output is correct
9 Correct 1050 ms 205040 KB Output is correct
10 Correct 1092 ms 202444 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 180908 KB Output is correct
2 Correct 1516 ms 195004 KB Output is correct
3 Correct 2654 ms 190116 KB Output is correct
4 Correct 864 ms 193708 KB Output is correct
5 Correct 1337 ms 193412 KB Output is correct
6 Correct 1461 ms 192736 KB Output is correct
7 Correct 2646 ms 188988 KB Output is correct
8 Correct 871 ms 192860 KB Output is correct
9 Correct 1343 ms 193100 KB Output is correct
10 Correct 1355 ms 192772 KB Output is correct
11 Correct 2610 ms 188976 KB Output is correct
12 Correct 321 ms 180536 KB Output is correct
13 Correct 1256 ms 236520 KB Output is correct
14 Correct 1445 ms 239616 KB Output is correct
15 Correct 1124 ms 236276 KB Output is correct
16 Correct 1296 ms 264088 KB Output is correct
17 Correct 1341 ms 240832 KB Output is correct
18 Correct 1344 ms 201172 KB Output is correct
19 Correct 1098 ms 201424 KB Output is correct
20 Correct 1050 ms 205040 KB Output is correct
21 Correct 1092 ms 202444 KB Output is correct
22 Correct 6675 ms 241992 KB Output is correct
23 Correct 3869 ms 244344 KB Output is correct
24 Correct 7025 ms 245348 KB Output is correct
25 Correct 6014 ms 248792 KB Output is correct
26 Execution timed out 8093 ms 245424 KB Time limit exceeded
27 Halted 0 ms 0 KB -