oj.uz

Submission #498120

# Submission time Handle Problem Language Result Execution time Memory
498120 2021-12-24T12:04:31 Z Deepesson Factories (JOI14_factories) C++17
100 / 100
 4234 ms 201940 KB 
#include <bits/stdc++.h>
#define MAX 505000
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
bool existe[MAX];
int dfs(int pos,int prev){
    int size=1;
    for(auto&x:con[pos]){
        if(x.first==prev||existe[x.first])continue;
        size+=dfs(x.first,pos);
    }
    return size;
}
int centroide=0;
int find(int pos,int prev,int sz){
    int size=1;
    int max=0;
    for(auto&x:con[pos]){
        if(x.first==prev||existe[x.first])continue;
        int b = find(x.first,pos,sz);
        max=std::max(max,b);
        size+=b;
    }
    max=std::max(max,sz-size);
    if(max<=sz/2)centroide=pos;
    return size;
}
int conna[MAX];
int nivel[MAX];
long long dists[MAX][25];
void explora(int pos,int prev,int lvl,long long dist){
    dists[pos][lvl]=dist;
    for(auto&x:con[pos]){
        if(x.first==prev||existe[x.first])continue;
        explora(x.first,pos,lvl,dist+x.second);
    }
}
void Decompor(int x,int lvl=0,int prev=-1){
    int tam=dfs(x,-1);
    find(x,-1,tam);
    int c = centroide;
    explora(c,-1,lvl,0);
    nivel[c]=lvl;
    existe[c]=true;
    conna[c]=prev;
    for(auto&x:con[c]){
        if(existe[x.first])continue;
        Decompor(x.first,lvl+1,c);
    }
}
long long tabela[MAX];
void Add(int p){
    int o=p;
    int nv = nivel[p];
    while(p!=-1){
        tabela[p]=std::min(tabela[p],dists[o][nv]);
        --nv;
        p=conna[p];
    }
}
void Zera(int p){
    while(p!=-1){
        tabela[p]=1LL<<50LL;
        p=conna[p];
    }
}
long long Check(int p){
    int o=p;
    int nv = nivel[p];
    long long ans=1LL<<50LL;
    while(p!=-1){
        ans=std::min(ans,tabela[p]+dists[o][nv]);
        --nv;
        p=conna[p];
    }
    return ans;
}
void Init(int N,int A[],int B[],int D[]){
    for(int i=0;i!=N-1;++i){
        int a = A[i],b=B[i],c=D[i];
        con[a].push_back({b,c});
        con[b].push_back({a,c});
    }
    Decompor(0);
    for(auto&x:tabela)x=1LL<<50LL;
}
long long Query(int S,int X[],int T,int Y[]){
    for(int i=0;i!=S;++i){
        Add(X[i]);
    }
    long long ans=1LL<<50LL;
    for(int i=0;i!=T;++i){
        ans=std::min(ans,Check(Y[i]));
    }
    for(int i=0;i!=S;++i){
        Zera(X[i]);
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16640 KB Output is correct
2 Correct 277 ms 25476 KB Output is correct
3 Correct 310 ms 25488 KB Output is correct
4 Correct 301 ms 25484 KB Output is correct
5 Correct 324 ms 26048 KB Output is correct
6 Correct 224 ms 34760 KB Output is correct
7 Correct 313 ms 34936 KB Output is correct
8 Correct 309 ms 34920 KB Output is correct
9 Correct 324 ms 35172 KB Output is correct
10 Correct 227 ms 34984 KB Output is correct
11 Correct 313 ms 34956 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16272 KB Output is correct
2 Correct 1663 ms 149840 KB Output is correct
3 Correct 2734 ms 152336 KB Output is correct
4 Correct 629 ms 168836 KB Output is correct
5 Correct 3436 ms 199436 KB Output is correct
6 Correct 2719 ms 172256 KB Output is correct
7 Correct 804 ms 65244 KB Output is correct
8 Correct 363 ms 65828 KB Output is correct
9 Correct 870 ms 69796 KB Output is correct
10 Correct 795 ms 66564 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 16640 KB Output is correct
2 Correct 277 ms 25476 KB Output is correct
3 Correct 310 ms 25488 KB Output is correct
4 Correct 301 ms 25484 KB Output is correct
5 Correct 324 ms 26048 KB Output is correct
6 Correct 224 ms 34760 KB Output is correct
7 Correct 313 ms 34936 KB Output is correct
8 Correct 309 ms 34920 KB Output is correct
9 Correct 324 ms 35172 KB Output is correct
10 Correct 227 ms 34984 KB Output is correct
11 Correct 313 ms 34956 KB Output is correct
12 Correct 9 ms 16272 KB Output is correct
13 Correct 1663 ms 149840 KB Output is correct
14 Correct 2734 ms 152336 KB Output is correct
15 Correct 629 ms 168836 KB Output is correct
16 Correct 3436 ms 199436 KB Output is correct
17 Correct 2719 ms 172256 KB Output is correct
18 Correct 804 ms 65244 KB Output is correct
19 Correct 363 ms 65828 KB Output is correct
20 Correct 870 ms 69796 KB Output is correct
21 Correct 795 ms 66564 KB Output is correct
22 Correct 1944 ms 175672 KB Output is correct
23 Correct 2024 ms 178452 KB Output is correct
24 Correct 3161 ms 178240 KB Output is correct
25 Correct 3426 ms 182064 KB Output is correct
26 Correct 3813 ms 178024 KB Output is correct
27 Correct 4234 ms 201940 KB Output is correct
28 Correct 763 ms 177680 KB Output is correct
29 Correct 3408 ms 177900 KB Output is correct
30 Correct 3728 ms 177352 KB Output is correct
31 Correct 3404 ms 178064 KB Output is correct
32 Correct 929 ms 70576 KB Output is correct
33 Correct 369 ms 66228 KB Output is correct
34 Correct 651 ms 62988 KB Output is correct
35 Correct 630 ms 63048 KB Output is correct
36 Correct 814 ms 63660 KB Output is correct
37 Correct 859 ms 63528 KB Output is correct