oj.uz

Submission #422555

# Submission time Handle Problem Language Result Execution time Memory
422555 2021-06-10T08:31:05 Z juggernaut Factories (JOI14_factories) C++17
100 / 100
 4643 ms 138828 KB 
#pragma GCC optimize("Ofast")
#include"factories.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
template<class T>void umin(T &a,T b){if(b<a)a=b;}
using namespace std;
typedef long long ll;
vector<pair<int,int>>g[500001];
int sz[500001];
bool black[500001];
void build_sz(int v,int p){
    sz[v]=1;
    for(auto &[to,wegiht]:g[v])if(to!=p&&!black[to]){
        build_sz(to,v);
        sz[v]+=sz[to];
    }
}
int get_centroid(int v,int p){
    int siz=sz[v]>>1;
    while(true){
        bool can=true;
        for(auto &[to,weight]:g[v]){
            if(black[to]||to==p)continue;
            if(sz[to]>siz){
                can=false;
                p=v;
                v=to;
                break;
            }
        }
        if(can)return v;
    }
}
ll dist[20][500001];
void build_dist(int v,int p,int lv){
    for(auto &[to,weight]:g[v])if(to!=p&&!black[to]){
        dist[lv][to]=dist[lv][v]+weight;
        build_dist(to,v,lv);
    }
}
int parent[500001];
int level[500001];
ll mn[500001];
int n;
void decompose(int centroid,int parent_centroid){
    build_sz(centroid,0);
    centroid=get_centroid(centroid,0);
    parent[centroid]=parent_centroid;
    level[centroid]=level[parent_centroid]+1;
    build_dist(centroid,0,level[centroid]);
    black[centroid]=true;
    for(auto &[to,weight]:g[centroid])if(!black[to])decompose(to,centroid);
}
void Init(int n,int a[],int b[],int c[]){
    ::n=n;
    for(int i=0;i<n-1;i++){
        int &x=a[i];
        int &y=b[i];
        int &z=c[i];
        g[x+1].emplace_back(y+1,z);
        g[y+1].emplace_back(x+1,z);
    }
    level[0]=-1;
    decompose(1,0);
    for(int i=1;i<=n;i++)mn[i]=1e15;
}
ll Query(int s,int x[],int t,int y[]){
    for(int i=0;i<s;i++){
        int ver=x[i]+1;
        while(ver){
            umin(mn[ver],dist[level[ver]][x[i]+1]);
            ver=parent[ver];
        }
    }
    ll ans=1e15;
    for(int i=0;i<t;i++){
        int ver=y[i]+1;
        while(ver){
            umin(ans,mn[ver]+dist[level[ver]][y[i]+1]);
            ver=parent[ver];
        }
    }
    for(int i=0;i<s;i++){
        int ver=x[i]+1;
        while(ver){
            mn[ver]=1e15;
            ver=parent[ver];
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12364 KB Output is correct
2 Correct 339 ms 20968 KB Output is correct
3 Correct 385 ms 20904 KB Output is correct
4 Correct 369 ms 21008 KB Output is correct
5 Correct 413 ms 21048 KB Output is correct
6 Correct 238 ms 20548 KB Output is correct
7 Correct 381 ms 20876 KB Output is correct
8 Correct 392 ms 20892 KB Output is correct
9 Correct 413 ms 21080 KB Output is correct
10 Correct 243 ms 20424 KB Output is correct
11 Correct 386 ms 20992 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12312 KB Output is correct
2 Correct 1946 ms 108920 KB Output is correct
3 Correct 3050 ms 124024 KB Output is correct
4 Correct 653 ms 58528 KB Output is correct
5 Correct 4016 ms 134864 KB Output is correct
6 Correct 3100 ms 125536 KB Output is correct
7 Correct 1053 ms 41092 KB Output is correct
8 Correct 374 ms 30240 KB Output is correct
9 Correct 1198 ms 43528 KB Output is correct
10 Correct 1054 ms 42376 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12364 KB Output is correct
2 Correct 339 ms 20968 KB Output is correct
3 Correct 385 ms 20904 KB Output is correct
4 Correct 369 ms 21008 KB Output is correct
5 Correct 413 ms 21048 KB Output is correct
6 Correct 238 ms 20548 KB Output is correct
7 Correct 381 ms 20876 KB Output is correct
8 Correct 392 ms 20892 KB Output is correct
9 Correct 413 ms 21080 KB Output is correct
10 Correct 243 ms 20424 KB Output is correct
11 Correct 386 ms 20992 KB Output is correct
12 Correct 9 ms 12312 KB Output is correct
13 Correct 1946 ms 108920 KB Output is correct
14 Correct 3050 ms 124024 KB Output is correct
15 Correct 653 ms 58528 KB Output is correct
16 Correct 4016 ms 134864 KB Output is correct
17 Correct 3100 ms 125536 KB Output is correct
18 Correct 1053 ms 41092 KB Output is correct
19 Correct 374 ms 30240 KB Output is correct
20 Correct 1198 ms 43528 KB Output is correct
21 Correct 1054 ms 42376 KB Output is correct
22 Correct 2360 ms 109368 KB Output is correct
23 Correct 2585 ms 113756 KB Output is correct
24 Correct 3808 ms 126380 KB Output is correct
25 Correct 3820 ms 129556 KB Output is correct
26 Correct 3717 ms 126364 KB Output is correct
27 Correct 4643 ms 138828 KB Output is correct
28 Correct 823 ms 65192 KB Output is correct
29 Correct 3719 ms 128952 KB Output is correct
30 Correct 3856 ms 128608 KB Output is correct
31 Correct 3869 ms 128840 KB Output is correct
32 Correct 1245 ms 51288 KB Output is correct
33 Correct 370 ms 37828 KB Output is correct
34 Correct 817 ms 44040 KB Output is correct
35 Correct 843 ms 44000 KB Output is correct
36 Correct 1132 ms 46836 KB Output is correct
37 Correct 1083 ms 46860 KB Output is correct