Submission #445570

#	Time	Username	Problem	Language	Result	Execution time	Memory
445570		julian33	Factories (JOI14_factories)	C++14	100 / 100	4242 ms	213696 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif

#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);} 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxN=5e5+5,mxL=20; //make sure this is right
const int mod=1e9+7;

/*
build a virtual tree
for each node find the closest A and B
*/

vector<pii> graph[mxN];
vector<int> vt[mxN];

ll up[mxN][2],down[mxN][2],yes[mxN][2],bl[mxN][mxL],st[mxN],en[mxN],ht[mxN],dep[mxN],cur;
ll ans=1e18;

void dfs(int at,int p){
    bl[at][0]=~p?p:at;
    for(int i=1;i<mxL;i++)
        bl[at][i]=bl[bl[at][i-1]][i-1];
    st[at]=++cur;
    for(auto &[i,w]:graph[at]){
        if(i==p)
            continue;
        ht[i]=ht[at]+1;
        dep[i]=dep[at]+w;
        dfs(i,at);
    }
    en[at]=++cur;
}

int jump(int a,int k){
    for(int i=0;i<mxL;i++){
        if(k&(1<<i))
            a=bl[a][i];
    }
    return a;
}

int lca(int a,int b){
    if(ht[a]>ht[b])
        swap(a,b);
    int diff=ht[b]-ht[a];
    b=jump(b,diff);
    if(a==b)
        return a;
    for(int i=mxL-1;i>=0;i--){
        if(bl[a][i]!=bl[b][i]){
            a=bl[a][i];
            b=bl[b][i];
        }
    }
    return bl[a][0];
}

ll dist(int a,int b){
    return dep[b]-dep[a];
}

bool anc(int a,int b){
    return st[a]<=st[b] && en[a]>=en[b];
}

void dfs1(int at,int p){
    for(int &i:vt[at]){
        if(i==p)
            continue;
        dfs1(i,at);
        mina(down[at][0],down[i][0]+dist(at,i));
        mina(down[at][1],down[i][1]+dist(at,i));
    }
    if(yes[at][0])
        down[at][0]=0;
    if(yes[at][1])
        down[at][1]=0;
}

void dfs2(int at,int p){
    for(int &i:vt[at]){
        if(i==p)
            continue;
        up[i][0]=min(up[at][0],down[at][0])+dist(at,i);
        up[i][1]=min(up[at][1],down[at][1])+dist(at,i);
        dfs2(i,at);
    }
    mina(ans,min(up[at][0],down[at][0])+min(up[at][1],down[at][1]));
}

void solve(int root){
    ans=1e18;
    dfs1(root,-1);
    dfs2(root,-1);
}

void build(vector<int> a){
    sort(a.begin(),a.end(),[&](int x,int y){return st[x]<st[y];});
    int len=sz(a);
    for(int i=0;i<len-1;i++){
        a.pb(lca(a[i],a[i+1]));
    }
    sort(a.begin(),a.end(),[&](int x,int y){return st[x]<st[y];});
    a.resize(unique(a.begin(),a.end())-a.begin());
    for(auto &i:a){
        up[i][0]=up[i][1]=1e16;
        down[i][0]=down[i][1]=1e16;
        vt[i].clear();
    }
    stack<int> stk; stk.push(a[0]);
    for(int i=1;i<sz(a);i++){
        while(sz(stk)>=2 && !anc(stk.top(),a[i])){
            int k=stk.top(); stk.pop();
            vt[stk.top()].pb(k);
        }
        stk.push(a[i]);
    }
    while(sz(stk)>=2){
        int k=stk.top();
        stk.pop();
        vt[stk.top()].pb(k);
    }
    solve(stk.top());
}

void Init(int N, int A[], int B[], int D[]){
    for(int i=0;i<N-1;i++){
        graph[A[i]].pb({B[i],D[i]});
        graph[B[i]].pb({A[i],D[i]});
    }
    dfs(0,-1);
}

long long Query(int S, int X[], int T, int Y[]){
    vector<int> a;
    for(int i=0;i<S;i++){
        yes[X[i]][0]=1;
        a.pb(X[i]);
    }
    for(int i=0;i<T;i++){
        yes[Y[i]][1]=1;
        a.pb(Y[i]);
    }
    build(a);
    for(int i=0;i<S;i++){
        yes[X[i]][0]=0;
    }
    for(int i=0;i<T;i++){
        yes[Y[i]][1]=0;
    }
    return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:49:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |     for(auto &[i,w]:graph[at]){
      |               ^

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