oj.uz

답안 #62138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62138 2018-07-27T13:40:10 Z FutymyClone 공장들 (JOI14_factories) C++17
100 / 100
 7895 ms 229492 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

const int N = 5e5 + 5;
vector <pair <int, int> > g[N];
int h[N], child[N], par[N];
bool visited[N];
long long dist[20][N], ans[N];

void dfs (int u, int p) {
    child[u] = 1;
    for (auto v: g[u]) {
        if (v.first != p && !visited[v.first]) {
            dfs(v.first, u);
            child[u] += child[v.first];
        }
    }
}

int findcen (int u, int p, int sz) {
    for (auto v: g[u]) {
        if (v.first != p && !visited[v.first] && child[v.first] >= sz / 2) return findcen(v.first, u, sz);
    }

    return u;
}

void redfs (int level, int u, int p, int cost) {
    if (p != -1) dist[level][u] = dist[level][p] + cost;
    for (auto v: g[u]) {
        if (v.first != p && !visited[v.first]) {
            redfs(level, v.first, u, v.second);
        }
    }
}

void centroid (int root, int p) {
    dfs(root, -1);
    int cen = findcen(root, -1, child[root]);
    visited[cen] = true; par[cen] = p;
    if (p != -1) h[cen] = h[p] + 1;

    redfs(h[cen], cen, -1, 0);
    for (auto v: g[cen]) if (v.first != p && !visited[v.first]) centroid(v.first, cen);
}

void update (int u) {
    for (int v = u; v != -1; v = par[v])
        ans[v] = min(ans[v], dist[h[v]][u]);
}

long long query (int u) {
    long long res = 1e18;
    for (int v = u; v != -1; v = par[v])
        res = min(res, ans[v] + dist[h[v]][u]);

    return res;
}

void Init (int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        g[A[i]].push_back(make_pair(B[i], D[i]));
        g[B[i]].push_back(make_pair(A[i], D[i]));
    }

    for (int i = 0; i < N; i++) ans[i] = 1e18;
    centroid(0, -1);
}

long long Query (int S, int X[], int T, int Y[]) {
    if (S < T) {
        for (int i = 0; i < S; i++) update(X[i]);
        long long res = 1e18;
        for (int i = 0; i < T; i++) res = min(res, query(Y[i]));
        for (int i = 0; i < S; i++)
            for (int v = X[i]; v != -1; v = par[v])
                ans[v] = 1e18;

        return res;
    }
    else {
        for (int i = 0; i < T; i++) update(Y[i]);
        long long res = 1e18;
        for (int i = 0; i < S; i++) res = min(res, query(X[i]));
        for (int i = 0; i < T; i++)
            for (int v = Y[i]; v != -1; v = par[v])
                ans[v] = 1e18;

        return res;
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 12536 KB Output is correct
2 Correct 423 ms 20972 KB Output is correct
3 Correct 436 ms 21044 KB Output is correct
4 Correct 454 ms 21128 KB Output is correct
5 Correct 533 ms 21460 KB Output is correct
6 Correct 484 ms 21460 KB Output is correct
7 Correct 635 ms 21460 KB Output is correct
8 Correct 440 ms 21460 KB Output is correct
9 Correct 559 ms 21792 KB Output is correct
10 Correct 361 ms 21792 KB Output is correct
11 Correct 523 ms 21792 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 21792 KB Output is correct
2 Correct 3290 ms 111488 KB Output is correct
3 Correct 4835 ms 129984 KB Output is correct
4 Correct 1381 ms 129984 KB Output is correct
5 Correct 6500 ms 152756 KB Output is correct
6 Correct 4897 ms 152756 KB Output is correct
7 Correct 1701 ms 152756 KB Output is correct
8 Correct 571 ms 152756 KB Output is correct
9 Correct 1817 ms 152756 KB Output is correct
10 Correct 1595 ms 152756 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 12536 KB Output is correct
2 Correct 423 ms 20972 KB Output is correct
3 Correct 436 ms 21044 KB Output is correct
4 Correct 454 ms 21128 KB Output is correct
5 Correct 533 ms 21460 KB Output is correct
6 Correct 484 ms 21460 KB Output is correct
7 Correct 635 ms 21460 KB Output is correct
8 Correct 440 ms 21460 KB Output is correct
9 Correct 559 ms 21792 KB Output is correct
10 Correct 361 ms 21792 KB Output is correct
11 Correct 523 ms 21792 KB Output is correct
12 Correct 15 ms 21792 KB Output is correct
13 Correct 3290 ms 111488 KB Output is correct
14 Correct 4835 ms 129984 KB Output is correct
15 Correct 1381 ms 129984 KB Output is correct
16 Correct 6500 ms 152756 KB Output is correct
17 Correct 4897 ms 152756 KB Output is correct
18 Correct 1701 ms 152756 KB Output is correct
19 Correct 571 ms 152756 KB Output is correct
20 Correct 1817 ms 152756 KB Output is correct
21 Correct 1595 ms 152756 KB Output is correct
22 Correct 4126 ms 152756 KB Output is correct
23 Correct 3594 ms 152756 KB Output is correct
24 Correct 5527 ms 152756 KB Output is correct
25 Correct 6308 ms 152756 KB Output is correct
26 Correct 5921 ms 152756 KB Output is correct
27 Correct 7895 ms 152756 KB Output is correct
28 Correct 1505 ms 152756 KB Output is correct
29 Correct 5922 ms 180728 KB Output is correct
30 Correct 6059 ms 204524 KB Output is correct
31 Correct 6283 ms 229492 KB Output is correct
32 Correct 1836 ms 229492 KB Output is correct
33 Correct 629 ms 229492 KB Output is correct
34 Correct 1406 ms 229492 KB Output is correct
35 Correct 1218 ms 229492 KB Output is correct
36 Correct 1833 ms 229492 KB Output is correct
37 Correct 1741 ms 229492 KB Output is correct