oj.uz

Submission #222929

# Submission time Handle Problem Language Result Execution time Memory
222929 2020-04-14T10:57:29 Z mhy908 Factories (JOI14_factories) C++14
100 / 100
 6483 ms 370380 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, LL> pil;
const LL llinf=1987654321987654321;
pil arr[500010];
int n, qq, sz[500010];
vector<pil> link[500010], up[500010];
bool ch[500010];
void dfs(int num, int par){
    sz[num]=1;
    for(auto i:link[num]){
        if(i.F==par||ch[i.F])continue;
        dfs(i.F, num);
        sz[num]+=sz[i.F];
    }
}
int get_centroid(int num, int par, int nd){
    for(auto i:link[num]){
        if(!ch[i.F]&&par!=i.F&&sz[i.F]>nd)return get_centroid(i.F, num, nd);
    }
    return num;
}
void get_up(int rt, int num, int par, LL d){
    up[num].pb(mp(rt, d));
    for(auto i:link[num]){
        if(i.F!=par&&!ch[i.F])get_up(rt, i.F, num, d+i.S);
    }
}
void get_centroid_tree(int num){
    dfs(num, 0);
    int cen=get_centroid(num, 0, sz[num]/2);
    get_up(cen, cen, 0, 0);
    ch[cen]=true;
    for(auto i:link[cen]){
        if(!ch[i.F])get_centroid_tree(i.F);
    }
}
void Init(int N, int A[], int B[], int D[]){
	for(int i=0; i<N-1; i++){
		link[A[i]+1].pb(mp(B[i]+1, D[i]));
		link[B[i]+1].pb(mp(A[i]+1, D[i]));
	}
	get_centroid_tree(1);
}
LL Query(int S, int X[], int T, int Y[]){
    qq--;
    for(int i=0; i<S; i++){
        for(auto j:up[X[i]+1])arr[j.F]=min(arr[j.F], mp(qq, j.S));
    }
    LL ret=llinf;
    for(int i=0; i<T; i++){
        for(auto j:up[Y[i]+1]){
            if(arr[j.F].F==qq)ret=min(ret, arr[j.F].S+j.S);
        }
    }
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24192 KB Output is correct
2 Correct 421 ms 32992 KB Output is correct
3 Correct 479 ms 33528 KB Output is correct
4 Correct 447 ms 33528 KB Output is correct
5 Correct 461 ms 33912 KB Output is correct
6 Correct 338 ms 37320 KB Output is correct
7 Correct 455 ms 38392 KB Output is correct
8 Correct 458 ms 38520 KB Output is correct
9 Correct 458 ms 38776 KB Output is correct
10 Correct 360 ms 37496 KB Output is correct
11 Correct 452 ms 38392 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24064 KB Output is correct
2 Correct 3496 ms 199632 KB Output is correct
3 Correct 4784 ms 270736 KB Output is correct
4 Correct 1309 ms 94004 KB Output is correct
5 Correct 5965 ms 345396 KB Output is correct
6 Correct 5033 ms 289584 KB Output is correct
7 Correct 1523 ms 83704 KB Output is correct
8 Correct 649 ms 60772 KB Output is correct
9 Correct 1613 ms 97964 KB Output is correct
10 Correct 1503 ms 85256 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24192 KB Output is correct
2 Correct 421 ms 32992 KB Output is correct
3 Correct 479 ms 33528 KB Output is correct
4 Correct 447 ms 33528 KB Output is correct
5 Correct 461 ms 33912 KB Output is correct
6 Correct 338 ms 37320 KB Output is correct
7 Correct 455 ms 38392 KB Output is correct
8 Correct 458 ms 38520 KB Output is correct
9 Correct 458 ms 38776 KB Output is correct
10 Correct 360 ms 37496 KB Output is correct
11 Correct 452 ms 38392 KB Output is correct
12 Correct 24 ms 24064 KB Output is correct
13 Correct 3496 ms 199632 KB Output is correct
14 Correct 4784 ms 270736 KB Output is correct
15 Correct 1309 ms 94004 KB Output is correct
16 Correct 5965 ms 345396 KB Output is correct
17 Correct 5033 ms 289584 KB Output is correct
18 Correct 1523 ms 83704 KB Output is correct
19 Correct 649 ms 60772 KB Output is correct
20 Correct 1613 ms 97964 KB Output is correct
21 Correct 1503 ms 85256 KB Output is correct
22 Correct 3724 ms 218720 KB Output is correct
23 Correct 3762 ms 222436 KB Output is correct
24 Correct 5365 ms 291216 KB Output is correct
25 Correct 5374 ms 294128 KB Output is correct
26 Correct 5355 ms 296860 KB Output is correct
27 Correct 6483 ms 370380 KB Output is correct
28 Correct 1412 ms 116004 KB Output is correct
29 Correct 4812 ms 296380 KB Output is correct
30 Correct 4876 ms 296568 KB Output is correct
31 Correct 4802 ms 296312 KB Output is correct
32 Correct 1427 ms 98352 KB Output is correct
33 Correct 646 ms 61260 KB Output is correct
34 Correct 1095 ms 76156 KB Output is correct
35 Correct 1221 ms 77180 KB Output is correct
36 Correct 1403 ms 82040 KB Output is correct
37 Correct 1425 ms 82040 KB Output is correct