제출 #480440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480440		MilosMilutinovic	공장들 (JOI14_factories)	C++14	0 / 100	7406 ms	154000 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=500050;
const int L=25;
vector<pair<int,int>> E[N];
int par[N][L],dep[N];
ll sum[N];
void DFS(int u,int p){
    dep[u]=dep[p]+1;
    par[u][0]=p;
    for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto e:E[u])if(e.first!=p){
        sum[e.first]=sum[u]+e.second;
        DFS(e.first,u);
    }
}
int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=L-1;i>=0;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
    for(int i=L-1;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
    return u==v?v:par[u][0];
}
ll Dist(int u,int v){return sum[u]+sum[v]-2*sum[LCA(u,v)];}
int sz[N];
bool was[N];
void DFSSZ(int u,int p){sz[u]=1;for(auto e:E[u])if(!was[e.first]&&e.first!=p)DFSSZ(e.first,u),sz[u]+=sz[e.first];}
int Find(int u,int p,int n){for(auto e:E[u])if(!was[e.first]&&e.first!=p&&sz[e.first]*2>n)return Find(e.first,u,n);return u;}
int Find(int u){DFSSZ(u,u);u=Find(u,u,sz[u]);was[u]=true;return u;}
vector<int> up[N];
void Update(int u,int p,int st){
    up[u].pb(st);
    for(auto e:E[u])if(e.first!=p&&!was[e.first])Update(e.first,u,st);
}
void Decompose(int u){
    u=Find(u);
    Update(u,u,u);
    for(auto e:E[u])if(!was[e.first])Decompose(e.first);
}
bool have[N];
ll dist[N];
void Init(int n,int a[],int b[],int d[]){
    for(int i=0;i<n-1;i++){
        a[i]++;b[i]++;
        E[a[i]].pb({b[i],d[i]});
        E[b[i]].pb({a[i],d[i]});
    }
    DFS(1,0);
    Decompose(1);
    for(int i=0;i<n;i++)dist[i]=1e18;
}
ll Query(int s,int x[],int t,int y[]){
    for(int i=0;i<s;i++){
        x[i]++;
        for(int u:up[x[i]])dist[u]=min(dist[u],Dist(x[i],u)),have[u]=true;
    }
    ll ans=1e18;
    for(int i=0;i<t;i++){
        y[i]++;
        for(int u:up[y[i]])ans=min(ans,dist[u]+Dist(y[i],u));
    }
    for(int i=0;i<s;i++)for(int u:up[x[i]])dist[u]=1e18,have[u]=false;
    return ans;
}

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