oj.uz

Submission #951564

# Submission time Handle Problem Language Result Execution time Memory
951564 2024-03-22T06:29:42 Z noyancanturk Factories (JOI14_factories) C++17
0 / 100
 29 ms 68176 KB 
#include "factories.h"

#pragma GCC optimize("O3,unroll-loops")
    
#include "bits/stdc++.h"
using namespace std;
    
#define pb push_back
    
const int lim=5e5+100;
const int64_t inf=lim*1e9;

using pii=pair<int,int64_t>;

vector<pii>v[lim];

bool vis[lim];
int tot,cent,layer,sz[lim];
int onlayer[lim],centpar[20][lim];
int64_t dist[20][lim];

inline int sbs(int node,int par){
    sz[node]=1;
    for(pii p:v[node]){
        if(!vis[p.first]&&(p.first^par)){
            sz[node]+=sbs(p.first,node);
        }
    }
    return sz[node];
}

inline int findcent(int node,int par){
    for(pii p:v[node]){
        if(!vis[p.first]&&(p.first^par)&&tot<2*sz[p.first]){
            return findcent(p.first,node);
        }
    }
    return node;
}

inline void distdfs(int node,int par){
    centpar[layer][node]=cent;
        for(pii p:v[node]){
        if(!vis[p.first]&&(p.first^par)){
            dist[layer][p.first]=dist[layer][node]+p.second;
            distdfs(p.first,node);
        }
    }
}

inline void decomp(int node,int dep=0){
    tot=sbs(node,-1);
    onlayer[cent=findcent(node,-1)]=dep;
    layer=dep;
    dist[layer][cent]=0;
    distdfs(cent,-1);
    vis[cent]=1;
    for(pii p:v[node]){
        if(!vis[p.first]){
            decomp(p.first,dep+1);
        }
    }
}

int64_t curvals[lim];

void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N-1;i++){
        v[A[i]].pb({B[i],D[i]});
        v[B[i]].pb({A[i],D[i]});
    }
    for(int i=0;i<N;i++){
        curvals[i]=inf;
    }
    decomp(0);
}

bool updated[lim];

long long Query(int S, int X[], int T, int Y[]) {
    vector<int>ulist;
    for(int i=0;i<S;i++){
        for(int j=onlayer[X[i]];0<=j;j--){
            if(!updated[centpar[j][X[i]]]){
                updated[centpar[j][X[i]]]=1;
                ulist.pb(centpar[j][X[i]]);
            }
            curvals[centpar[j][X[i]]]=min(curvals[centpar[j][X[i]]],dist[j][X[i]]);
        }
    }
    int64_t ans=inf;
    for(int i=0;i<T;i++){
        for(int j=onlayer[Y[i]];0<=j;j--){
            ans=min(ans,curvals[centpar[j][Y[i]]]+dist[j][Y[i]]);
        }
    }
    for(int i:ulist){
        curvals[i]=inf;
        updated[i]=0;
    }
    return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 68176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 64272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 68176 KB Output isn't correct
2 Halted 0 ms 0 KB -