oj.uz

답안 #422529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422529 2021-06-10T08:04:20 Z tengiz05 공장들 (JOI14_factories) C++17
33 / 100
 8000 ms 239520 KB 
#include "factories.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 500000, K = 22, M = 2 * N + 1;
std::vector<std::pair<int, int>> e[N];
i64 st[K + 1][M];
int lg[M + 1], n, P[N], timer;
i64 D[N];
i64 pos[M];
int order[N], timeStamp;
int par[N];
int dpar[N];
void dfs(int u, int p, i64 d = 0){
    order[timeStamp++] = u;
    par[u] = p;
    P[u] = timer;
    pos[timer++] = d;
    D[u] = d;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dpar[v] = w;
            dfs(v, u, d + w);
            pos[timer++] = d;
        }
    }
}
inline i64 dist(int u, int v) {
    int L = P[u], R = P[v];
    if (L > R) std::swap(L, R);
    int j = lg[R - L + 1];
    return D[u] + D[v] - std::min(st[j][L], st[j][R - (1 << j) + 1]);
}
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[0][i] = 2 * pos[i];
    for (int j = 1; j <= K; j++)
        for (int i = 0; i + (1 << j) <= M; i++)
            st[j][i] = std::min(st[j-1][i], st[j - 1][i + (1 << (j - 1))]);
}
i64 dp[N];
i64 Query(int S, int X[], int T, int Y[]) {
    if (S + T <= 20050) {
        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];
        dp[par[u]] = std::min(dp[par[u]], dp[u] + dpar[u]);
    }
    for (int i = 0; i < n; i++) {
        int u = order[i];
        dp[u] = std::min(dp[u], dp[par[u]] + dpar[u]);
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 164608 KB Output is correct
2 Correct 6759 ms 172772 KB Output is correct
3 Correct 2139 ms 172828 KB Output is correct
4 Correct 2511 ms 172868 KB Output is correct
5 Correct 6737 ms 173024 KB Output is correct
6 Correct 7081 ms 172856 KB Output is correct
7 Correct 2085 ms 172956 KB Output is correct
8 Correct 2579 ms 172908 KB Output is correct
9 Correct 6799 ms 173016 KB Output is correct
10 Correct 7040 ms 172796 KB Output is correct
11 Correct 2079 ms 173052 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 164508 KB Output is correct
2 Correct 1002 ms 215392 KB Output is correct
3 Correct 1089 ms 216928 KB Output is correct
4 Correct 861 ms 216060 KB Output is correct
5 Correct 1051 ms 239520 KB Output is correct
6 Correct 1055 ms 218248 KB Output is correct
7 Correct 1016 ms 183096 KB Output is correct
8 Correct 726 ms 183628 KB Output is correct
9 Correct 680 ms 186632 KB Output is correct
10 Correct 754 ms 184220 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 164608 KB Output is correct
2 Correct 6759 ms 172772 KB Output is correct
3 Correct 2139 ms 172828 KB Output is correct
4 Correct 2511 ms 172868 KB Output is correct
5 Correct 6737 ms 173024 KB Output is correct
6 Correct 7081 ms 172856 KB Output is correct
7 Correct 2085 ms 172956 KB Output is correct
8 Correct 2579 ms 172908 KB Output is correct
9 Correct 6799 ms 173016 KB Output is correct
10 Correct 7040 ms 172796 KB Output is correct
11 Correct 2079 ms 173052 KB Output is correct
12 Correct 96 ms 164508 KB Output is correct
13 Correct 1002 ms 215392 KB Output is correct
14 Correct 1089 ms 216928 KB Output is correct
15 Correct 861 ms 216060 KB Output is correct
16 Correct 1051 ms 239520 KB Output is correct
17 Correct 1055 ms 218248 KB Output is correct
18 Correct 1016 ms 183096 KB Output is correct
19 Correct 726 ms 183628 KB Output is correct
20 Correct 680 ms 186632 KB Output is correct
21 Correct 754 ms 184220 KB Output is correct
22 Execution timed out 8096 ms 220608 KB Time limit exceeded
23 Halted 0 ms 0 KB -