Submission #951592

#	Time	Username	Problem	Language	Result	Execution time	Memory
951592		noyancanturk	Factories (JOI14_factories)	C++17	100 / 100	3657 ms	222744 KiB

factories

#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){
    layer=dep;
    tot=sbs(node,-1);
    onlayer[cent=findcent(node,-1)]=dep;
    vis[cent]=1;
    dist[layer][cent]=0;
    distdfs(cent,-1);
    for(pii p:v[cent]){
        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);
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<S;i++){
        for(int j=onlayer[X[i]];0<=j;j--){
            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=0;i<S;i++){
        for(int j=onlayer[X[i]];0<=j;j--){
            curvals[centpar[j][X[i]]]=inf;
        }
    }
    return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67