제출 #656956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656956		bachhoangxuan	공장들 (JOI14_factories)	C++17	100 / 100	3121 ms	319864 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define piii pair<ll,pii>
#define se second
#define fi first
#define maxn 500005
#define maxl 22
const ll inf=1e18;
vector<pii> edge[maxn],adj[maxn];
ll n,q,sz,cnt,len,L[maxn],R[maxn],Min[2*maxn][maxl],cn[2*maxn],f[maxn],lg[2*maxn],dep[maxn];
int scc[maxn];
bool cmp(int a,int b){
    return L[a]<L[b];
}
void dfs(ll u,ll par){
    L[u]=++cnt;len++;
    f[u]=Min[len][0]=len;cn[len]=u;
    for(pii v:edge[u]){
        if(v.first==par) continue;
        dep[v.first]=dep[u]+v.second;
        dfs(v.first,u);
        Min[++len][0]=f[u];
    }
    R[u]=cnt;
}
ll lca(ll u,ll v){
    u=f[u];v=f[v];
    if(u>v) swap(u,v);
    ll p=lg[v-u+1],a=min(Min[u][p],Min[v-(1<<p)+1][p]);
    return cn[a];
}
ll getdist(ll u,ll v){
    return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void build_sparse(){
    for(ll i=2;i<=len;i++) lg[i]=lg[i/2]+1;
    for(ll i=1;i<20;i++){
        for(ll j=1;j<=(len-(1<<i)+1);j++) Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]);
    }
}
ll Min1[maxn],Min2[maxn];
void dfs2(int u){
    Min1[u]=Min2[u]=inf;
    for(pii v:adj[u]){
        dfs2(v.first);
        Min1[u]=min(Min1[u],Min1[v.first]+v.second);
        Min2[u]=min(Min2[u],Min2[v.first]+v.second);
    }
    if(scc[u]&1) Min1[u]=0;
    if(scc[u]&2) Min2[u]=0;
}
void redfs(int u,pii dt){
    Min1[u]=min(Min1[u],dt.first);Min2[u]=min(Min2[u],dt.second);
    for(pii v:adj[u]){
        redfs(v.first,{Min1[u]+v.second,Min2[u]+v.second});
    }
}
long long Query(int s,int xs[],int t,int yt[]){
    vector<int> node;
    for(int i=0;i<s;i++){scc[xs[i]+1]+=1;node.push_back(xs[i]+1);}
    for(int i=0;i<t;i++){scc[yt[i]+1]+=2;node.push_back(yt[i]+1);}
    sort(node.begin(),node.end(),cmp);
    for(int i=0;i<(s+t-1);i++) node.push_back(lca(node[i],node[i+1]));
    sort(node.begin(),node.end(),cmp);
    node.erase(unique(node.begin(),node.end()),node.end());
    int root=-1;vector<int> v;
    for(int x:node){
        while(!v.empty() && R[v.back()]<L[x]) v.pop_back();
        if(!v.empty()) adj[v.back()].push_back({x,dep[x]-dep[v.back()]});
        else root=x;
        v.push_back(x);
    }
    dfs2(root);redfs(root,{inf,inf});
    ll res=inf;
    for(int x:node) res=min(res,Min1[x]+Min2[x]);
    for(int x:node){scc[x]=0;adj[x].clear();Min1[x]=Min2[x]=0;}
    return res;
}
void Init(int N, int A[],int B[],int D[]) {
    n=N;
    for(ll i=0;i<n-1;i++){
        edge[A[i]+1].push_back({B[i]+1,D[i]});
        edge[B[i]+1].push_back({A[i]+1,D[i]});
    }
    dfs(1,0);build_sparse();
}

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