oj.uz

Submission #839516

# Submission time Handle Problem Language Result Execution time Memory
839516 2023-08-30T08:51:26 Z imarn Factories (JOI14_factories) C++14
100 / 100
 4408 ms 353452 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N=5e5+5;
vector<pair<int,ll>>g[N];
int sz[N]{0};
bool vis[N]{0};
ll dp[N]{0};
vector<pair<int,ll>>ancestor[N];
int getsize(int u,int p){
    sz[u]=1;
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        sz[u]+=getsize(v.f,u);
    }return sz[u];
}
int get_centroid(int u,int p,int n){
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        if(sz[v.f]*2>n)return get_centroid(v.f,u,n);
    }return u;
}
void gen_dist(int u,int p,int centroid,ll cur){
    for(auto v:g[u]){
        if(vis[v.f]||v.f==p)continue;
        gen_dist(v.f,u,centroid,cur+v.s);
    }ancestor[u].pb({centroid,cur});
}
void play(int u=0){
    int centroid=get_centroid(u,u,getsize(u,u));
    for(auto v:g[centroid]){
        if(vis[v.f])continue;
        gen_dist(v.f,centroid,centroid,v.s);
    }vis[centroid]=1;
    for(auto v:g[centroid]){
        if(vis[v.f])continue;
        play(v.f);
    }
}
void upd(int u){
    for(auto v:ancestor[u]){
        dp[v.f]=min(dp[v.f],v.s);
    }dp[u]=0;
}
ll qry(int u){
    ll ans=dp[u];
    for(auto v:ancestor[u]){
        ans=min(ans,v.s+dp[v.f]);
    }return ans;
}
void Init(int N,int A[],int B[],int D[]){
    for(int i=0;i<N;i++)dp[i]=1e16;
    for(int i=0;i<N-1;i++){
        g[A[i]].pb({B[i],D[i]});g[B[i]].pb({A[i],D[i]});
    }play();
}
long long Query(int S,int X[],int T,int Y[]){
    for(int i=0;i<S;i++){
        upd(X[i]);
    }
    ll ans=1e16;
    for(int i=0;i<T;i++){
        ans=min(ans,qry(Y[i]));
    }
    for(int i=0;i<S;i++){
        dp[X[i]]=1e16;
        for(auto it : ancestor[X[i]])dp[it.f]=1e16;
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24276 KB Output is correct
2 Correct 201 ms 42292 KB Output is correct
3 Correct 219 ms 42744 KB Output is correct
4 Correct 211 ms 42680 KB Output is correct
5 Correct 222 ms 43176 KB Output is correct
6 Correct 154 ms 41700 KB Output is correct
7 Correct 223 ms 42720 KB Output is correct
8 Correct 218 ms 42772 KB Output is correct
9 Correct 230 ms 43264 KB Output is correct
10 Correct 152 ms 41680 KB Output is correct
11 Correct 209 ms 42688 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24020 KB Output is correct
2 Correct 1935 ms 203840 KB Output is correct
3 Correct 3215 ms 248804 KB Output is correct
4 Correct 614 ms 100200 KB Output is correct
5 Correct 3883 ms 343628 KB Output is correct
6 Correct 3168 ms 250672 KB Output is correct
7 Correct 811 ms 82508 KB Output is correct
8 Correct 253 ms 58364 KB Output is correct
9 Correct 927 ms 88984 KB Output is correct
10 Correct 843 ms 83972 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24276 KB Output is correct
2 Correct 201 ms 42292 KB Output is correct
3 Correct 219 ms 42744 KB Output is correct
4 Correct 211 ms 42680 KB Output is correct
5 Correct 222 ms 43176 KB Output is correct
6 Correct 154 ms 41700 KB Output is correct
7 Correct 223 ms 42720 KB Output is correct
8 Correct 218 ms 42772 KB Output is correct
9 Correct 230 ms 43264 KB Output is correct
10 Correct 152 ms 41680 KB Output is correct
11 Correct 209 ms 42688 KB Output is correct
12 Correct 14 ms 24020 KB Output is correct
13 Correct 1935 ms 203840 KB Output is correct
14 Correct 3215 ms 248804 KB Output is correct
15 Correct 614 ms 100200 KB Output is correct
16 Correct 3883 ms 343628 KB Output is correct
17 Correct 3168 ms 250672 KB Output is correct
18 Correct 811 ms 82508 KB Output is correct
19 Correct 253 ms 58364 KB Output is correct
20 Correct 927 ms 88984 KB Output is correct
21 Correct 843 ms 83972 KB Output is correct
22 Correct 2274 ms 208600 KB Output is correct
23 Correct 2345 ms 215340 KB Output is correct
24 Correct 3703 ms 257300 KB Output is correct
25 Correct 3613 ms 260884 KB Output is correct
26 Correct 3549 ms 257928 KB Output is correct
27 Correct 4408 ms 353452 KB Output is correct
28 Correct 694 ms 110612 KB Output is correct
29 Correct 3793 ms 257660 KB Output is correct
30 Correct 3524 ms 257592 KB Output is correct
31 Correct 3485 ms 257452 KB Output is correct
32 Correct 1029 ms 89288 KB Output is correct
33 Correct 255 ms 58812 KB Output is correct
34 Correct 517 ms 72184 KB Output is correct
35 Correct 523 ms 73164 KB Output is correct
36 Correct 736 ms 80900 KB Output is correct
37 Correct 752 ms 80920 KB Output is correct