Submission #498120

#	Time	Username	Problem	Language	Result	Execution time	Memory
498120		Deepesson	공장들 (JOI14_factories)	C++17	100 / 100	4234 ms	201940 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67