Submission #883596

#	Time	Username	Problem	Language	Result	Execution time	Memory
883596		Warinchai	Factories (JOI14_factories)	C++14	0 / 100	21 ms	74324 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,long long> >adj[500005];
int sz[500005];
bool used[500005];
long long pl[20][500005];
int pa[500005];
int lv[500005];
long long mn[500005];
int dfssz(int u,int p=-1){
    sz[u]=1;
    for(auto v:adj[u])if(v.first!=p&&!used[v.first])sz[u]+=dfssz(v.first,u);
    return sz[u];
}
int centroid(int u,int rsz,int p=-1){
    for(auto v:adj[u])if(v.first!=p&&!used[v.first]&&sz[v.first]>rsz/2)return centroid(v.first,rsz,u);
    return u;
}
void dfs(int u,long long d,int lvl,int p=-1){
    pl[lvl][u]=d;
    for(auto v:adj[u])if(v.first!=p&&!used[v.first])dfs(v.first,d+v.second,lvl+1,u);
}
void decom(int u,int lvl,int p=-1){
    u=centroid(u,dfssz(u));
    pa[u]=p;
    lv[u]=lvl;
    used[u]=true;
    dfs(u,0,lvl);
    for(auto v:adj[u])if(v.first!=p&&!used[v.first])decom(v.first,lvl+1,u);
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N;i++)adj[B[i]].push_back({A[i],D[i]}),adj[A[i]].push_back({B[i],D[i]});
    decom(1,1);
    for(int i=0;i<=N;i++)mn[i]=LLONG_MAX;
}
long long fans(int x){
    long long ans=LLONG_MAX;
    while(x!=-1){
        ans=min(ans,mn[x]);
        x=pa[x];
    }
    return ans;
}
void upd(int x){
    int st=x;
    while(x!=-1){
        mn[x]=min(mn[x],pl[lv[x]][st]);
        x=pa[x];
    }
}
void rvupd(int x){
    while(x!=-1){
        mn[x]=LLONG_MAX;
        x=pa[x];
    }
}
long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<S;i++)upd(X[i]);
    long long ans=LLONG_MAX;
    for(int i=0;i<T;i++)ans=min(ans,fans(Y[i]));
    for(int i=0;i<S;i++)rvupd(X[i]);
    return ans;
}

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