제출 #656663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
656663		bachhoangxuan	공장들 (JOI14_factories)	C++17	0 / 100	18 ms	24276 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 1000005
#define maxl 22
const ll inf=1e18;
vector<pii> edge[maxn];
pii ver[4*maxn];
piii pr[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],dt[maxn];
ll root[maxn];
bool cmp(pii a,pii b){
    return L[a.first]<L[b.first];
}
void dfs(ll u,ll par){
    L[u]=++cnt;len++;dt[u]=dt[par]+1;
    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 res=inf;
ll findroot(ll u){
    if(u!=root[u]) return root[u]=findroot(root[u]);
    return u;
}
void unions(ll u,ll v){
    u=findroot(u);v=findroot(v);
    ll a=lca(pr[u].fi,pr[v].fi),d=getdist(pr[u].fi,pr[v].fi);
    res=min(res,min(pr[u].se.se+pr[v].se.fi,pr[u].se.fi+pr[v].se.se)+d);
    root[v]=u;
    pr[u].se.fi=min(inf,min(pr[u].se.fi+getdist(a,pr[u].fi),pr[v].se.fi+getdist(a,pr[v].fi)));
    pr[u].se.se=min(inf,min(pr[u].se.se+getdist(a,pr[u].fi),pr[v].se.se+getdist(a,pr[v].fi)));
    pr[u].fi=a;
}
pii cal(ll l,ll r){
    if(l==r){
        if(ver[l].second==1) return {0,inf};
        else return {inf,0};
    }
    ll lt=l+1;
    vector<piii> pp;
    while(lt<=r){
        ll nxt=upper_bound(ver+l,ver+r+1,make_pair(R[ver[lt].first],2LL))-ver-1;
        pp.push_back({ver[lt].first,cal(lt,nxt)});lt=nxt+1;
    }
    vector<piii> x;
    for(ll i=0;i<(ll)pp.size();i++){
        root[pp[i].fi]=pp[i].fi;
        pr[pp[i].fi]=pp[i];
    }
    for(ll i=0;i<(ll)pp.size()-1;i++) x.push_back({n-dt[lca(pp[i].fi,pp[i+1].fi)],{pp[i].fi,pp[i+1].fi}});
    sort(x.begin(),x.end());
    for(auto k:x){
        unions(k.se.fi,k.se.se);
    }
    pii ans={inf,inf};
    if(ver[l].second==1) ans.first=0;
    else ans.second=0;
    for(ll i=0;i<(ll)pp.size();i++){
        if(ver[l].second==1) ans.second=min(ans.second,pp[i].se.se+dep[pp[i].fi]-dep[ver[l].fi]);
        else ans.first=min(ans.first,pp[i].se.fi+dep[pp[i].fi]-dep[ver[l].fi]);
    }
    if(ver[l].second==1) res=min(res,ans.second);
    else res=min(res,ans.first);
    return ans;
}
long long Query(int s,int xs[],int t,int yt[]){
    /*
    sz=s+t;
    for(ll i=1;i<=s;i++){
        ver[i].first=xs[i-1];ver[i].first++;
        ver[i].second=1;
    }
    for(ll i=1;i<=t;i++){
        ver[s+i].first=yt[i-1];ver[s+i].first++;
        ver[s+i].second=2;
    }
    sort(ver+1,ver+sz+1,cmp);res=inf;
    ll l=1;
    vector<piii> pp;
    while(l<=sz){
        ll nxt=upper_bound(ver+1,ver+sz+1,make_pair(R[ver[l].first],2LL))-ver-1;
        pp.push_back({ver[l].first,cal(l,nxt)});l=nxt+1;
    }
   vector<piii> x;
    for(ll i=0;i<(ll)pp.size();i++){
        root[pp[i].fi]=pp[i].fi;
        pr[pp[i].fi]=pp[i];
    }
    for(ll i=0;i<(ll)pp.size()-1;i++) x.push_back({n-dt[lca(pp[i].fi,pp[i+1].fi)],{pp[i].fi,pp[i+1].fi}});
    sort(x.begin(),x.end());
    for(auto k:x) unions(k.se.fi,k.se.se);
    return res;
    */
    return 0LL;
}
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: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67