oj.uz

Submission #413446

# Submission time Handle Problem Language Result Execution time Memory
413446 2021-05-28T17:55:17 Z souvenir_vayne Factories (JOI14_factories) C++14
100 / 100
 5290 ms 368152 KB 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
const long long N = 5e5 + 5, INF = 1e18 + 5;
 
long long n, cnt[N], mina[N], ans;
bool blocked[N];
 
struct Edge{
    long long b, w;
};
 
vector<Edge> tree[N];
vector<Edge> parent[N];
 
void subtreecnt(int v, int p){
    cnt[v] = 1;
 
    for(auto e : tree[v]){
        if(e.b != p && !blocked[e.b]){
            subtreecnt(e.b, v);
            cnt[v] += cnt[e.b];
        }
    }
}
 
int findcentroid(int v, int p, int root){
    for(auto e : tree[v]){
        if(e.b != p && !blocked[e.b] && cnt[e.b] > cnt[root] / 2){
            return findcentroid(e.b, v, root);
        }
    }
    return v;
}
 
void findpaths(int v, int p, int centroid, long long curw){
    parent[v].push_back({centroid, curw});
 
    for(auto e : tree[v]){
        if(e.b != p && !blocked[e.b]) findpaths(e.b, v, centroid, curw + e.w);
    }
}
 
void decomp(int v){
    subtreecnt(v, -1);
 
    int centroid = findcentroid(v, -1, v);
 
    findpaths(centroid, -1, centroid, 0);
 
    blocked[centroid] = true;
 
    for(auto e : tree[centroid]) if(!blocked[e.b]) decomp(e.b);
}
 
void Init(int n, int a[], int b[], int d[]){
    for(int i = 0; i < n - 1; i++){
        tree[a[i]].push_back({b[i], d[i]});
        tree[b[i]].push_back({a[i], d[i]});
    }
 
    decomp(0);
 
 
    fill(mina, mina + N, INF);
}
 
long long Query(int s, int x[], int t, int y[]){
    ans = INF;
 
    for(int i = 0; i < s; i++){
        for(auto e : parent[x[i]]){
            mina[e.b] = min(mina[e.b], e.w);
        }
    }
 
    for(int i = 0; i < t; i++){
        for(auto e : parent[y[i]]){
            ans = min(ans, mina[e.b] + e.w);
        }
    }
 
    for(int i = 0; i < s; i++){
        for(auto e : parent[x[i]]){
            mina[e.b] = INF;
        }
    }
 
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27980 KB Output is correct
2 Correct 351 ms 38796 KB Output is correct
3 Correct 362 ms 37528 KB Output is correct
4 Correct 374 ms 37628 KB Output is correct
5 Correct 450 ms 37884 KB Output is correct
6 Correct 274 ms 36560 KB Output is correct
7 Correct 372 ms 37536 KB Output is correct
8 Correct 389 ms 37560 KB Output is correct
9 Correct 394 ms 37884 KB Output is correct
10 Correct 277 ms 36572 KB Output is correct
11 Correct 370 ms 37604 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27844 KB Output is correct
2 Correct 2529 ms 197796 KB Output is correct
3 Correct 3663 ms 268340 KB Output is correct
4 Correct 965 ms 110060 KB Output is correct
5 Correct 4420 ms 361800 KB Output is correct
6 Correct 3693 ms 287640 KB Output is correct
7 Correct 1156 ms 86600 KB Output is correct
8 Correct 499 ms 63560 KB Output is correct
9 Correct 1298 ms 100640 KB Output is correct
10 Correct 1189 ms 87764 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 27980 KB Output is correct
2 Correct 351 ms 38796 KB Output is correct
3 Correct 362 ms 37528 KB Output is correct
4 Correct 374 ms 37628 KB Output is correct
5 Correct 450 ms 37884 KB Output is correct
6 Correct 274 ms 36560 KB Output is correct
7 Correct 372 ms 37536 KB Output is correct
8 Correct 389 ms 37560 KB Output is correct
9 Correct 394 ms 37884 KB Output is correct
10 Correct 277 ms 36572 KB Output is correct
11 Correct 370 ms 37604 KB Output is correct
12 Correct 17 ms 27844 KB Output is correct
13 Correct 2529 ms 197796 KB Output is correct
14 Correct 3663 ms 268340 KB Output is correct
15 Correct 965 ms 110060 KB Output is correct
16 Correct 4420 ms 361800 KB Output is correct
17 Correct 3693 ms 287640 KB Output is correct
18 Correct 1156 ms 86600 KB Output is correct
19 Correct 499 ms 63560 KB Output is correct
20 Correct 1298 ms 100640 KB Output is correct
21 Correct 1189 ms 87764 KB Output is correct
22 Correct 3192 ms 221632 KB Output is correct
23 Correct 3209 ms 226512 KB Output is correct
24 Correct 4736 ms 293840 KB Output is correct
25 Correct 4707 ms 298076 KB Output is correct
26 Correct 4419 ms 294920 KB Output is correct
27 Correct 5290 ms 368152 KB Output is correct
28 Correct 1391 ms 120624 KB Output is correct
29 Correct 4404 ms 294172 KB Output is correct
30 Correct 4620 ms 294304 KB Output is correct
31 Correct 4550 ms 294284 KB Output is correct
32 Correct 1420 ms 100832 KB Output is correct
33 Correct 546 ms 63852 KB Output is correct
34 Correct 970 ms 78844 KB Output is correct
35 Correct 984 ms 79580 KB Output is correct
36 Correct 1269 ms 84724 KB Output is correct
37 Correct 1232 ms 84668 KB Output is correct