oj.uz

Submission #95287

# Submission time Handle Problem Language Result Execution time Memory
95287 2019-01-29T14:38:51 Z dalgerok Factories (JOI14_factories) C++14
100 / 100
 7525 ms 182384 KB 
#include<bits/stdc++.h>
using namespace std;

const int M = 5e5 + 1, K = 20;
const long long INF = 9e18;


int p[M], d[M];
long long dist[K][M], ans[M];
bool used[M];
vector < pair < int, int > > g[M];

int dfs(int v, int size, int &center, int pr = -1){
    int sz = 1;
    for(auto it : g[v]){
        int to = it.first;
        if(to != pr && !used[to]){
            sz += dfs(to, size, center, v);
        }
    }
    if(center == -1 && sz >= size / 2){
        center = v;
    }
    return sz;
}

void dfs1(int v, int depth, int pr = -1, long long len = 0){
    dist[depth][v] = len;
    for(auto it : g[v]){
        int to = it.first, val = it.second;
        if(to != pr && !used[to]){
            dfs1(to, depth, v, len + val);
        }
    }
}

void build(int v, int pr = -1, int depth = 0){
    int center = -1, tmp = 0;
    dfs(v, dfs(v, 0, tmp), center);
    dfs1(center, depth);
    used[center] = true;
    d[center] = depth;
    p[center] = pr;
    for(auto it : g[center]){
        int to = it.first;
        if(!used[to]){
            build(to, center, depth + 1);
        }
    }
}

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 < 5e5; i++){
        ans[i] = INF;
    }
    build(0);
}

long long Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; i++){
        int cur = X[i];
        while(cur != -1){
            ans[cur] = min(ans[cur], dist[d[cur]][X[i]]);
            cur = p[cur];
        }
    }
    long long mn = INF;
    for(int i = 0; i < T; i++){
        int cur = Y[i];
        while(cur != -1){
            mn = min(mn, dist[d[cur]][Y[i]] + ans[cur]);
            cur = p[cur];
        }
    }
    for(int i = 0; i < S; i++){
        int cur = X[i];
        while(cur != -1){
            ans[cur] = INF;
            cur = p[cur];
        }
    }
    return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16376 KB Output is correct
2 Correct 318 ms 24948 KB Output is correct
3 Correct 349 ms 24924 KB Output is correct
4 Correct 354 ms 34552 KB Output is correct
5 Correct 379 ms 34864 KB Output is correct
6 Correct 255 ms 33912 KB Output is correct
7 Correct 357 ms 34424 KB Output is correct
8 Correct 364 ms 34552 KB Output is correct
9 Correct 383 ms 34844 KB Output is correct
10 Correct 246 ms 33912 KB Output is correct
11 Correct 348 ms 34496 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16248 KB Output is correct
2 Correct 2919 ms 113168 KB Output is correct
3 Correct 5301 ms 132984 KB Output is correct
4 Correct 1054 ms 60892 KB Output is correct
5 Correct 5245 ms 179616 KB Output is correct
6 Correct 4280 ms 152440 KB Output is correct
7 Correct 1093 ms 59512 KB Output is correct
8 Correct 360 ms 47852 KB Output is correct
9 Correct 1598 ms 64232 KB Output is correct
10 Correct 1134 ms 60920 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16376 KB Output is correct
2 Correct 318 ms 24948 KB Output is correct
3 Correct 349 ms 24924 KB Output is correct
4 Correct 354 ms 34552 KB Output is correct
5 Correct 379 ms 34864 KB Output is correct
6 Correct 255 ms 33912 KB Output is correct
7 Correct 357 ms 34424 KB Output is correct
8 Correct 364 ms 34552 KB Output is correct
9 Correct 383 ms 34844 KB Output is correct
10 Correct 246 ms 33912 KB Output is correct
11 Correct 348 ms 34496 KB Output is correct
12 Correct 17 ms 16248 KB Output is correct
13 Correct 2919 ms 113168 KB Output is correct
14 Correct 5301 ms 132984 KB Output is correct
15 Correct 1054 ms 60892 KB Output is correct
16 Correct 5245 ms 179616 KB Output is correct
17 Correct 4280 ms 152440 KB Output is correct
18 Correct 1093 ms 59512 KB Output is correct
19 Correct 360 ms 47852 KB Output is correct
20 Correct 1598 ms 64232 KB Output is correct
21 Correct 1134 ms 60920 KB Output is correct
22 Correct 3130 ms 137544 KB Output is correct
23 Correct 3474 ms 142520 KB Output is correct
24 Correct 5822 ms 158304 KB Output is correct
25 Correct 6139 ms 162432 KB Output is correct
26 Correct 4844 ms 158816 KB Output is correct
27 Correct 7525 ms 182384 KB Output is correct
28 Correct 1357 ms 89372 KB Output is correct
29 Correct 6002 ms 158324 KB Output is correct
30 Correct 5971 ms 157700 KB Output is correct
31 Correct 5471 ms 158212 KB Output is correct
32 Correct 1298 ms 65272 KB Output is correct
33 Correct 402 ms 48236 KB Output is correct
34 Correct 847 ms 54676 KB Output is correct
35 Correct 879 ms 54700 KB Output is correct
36 Correct 1299 ms 57720 KB Output is correct
37 Correct 1226 ms 57884 KB Output is correct