Submission #233691

#	Time	Username	Problem	Language	Result	Execution time	Memory
233691		lfsfrlvng	Factories (JOI14_factories)	C++14	100 / 100	4089 ms	139612 KiB

factories

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,long long>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);

//#define unx xun

#ifndef unx
#include "factories.h"
const int N=500010;
#endif // unx

#ifdef unx
const int N=100010;
#endif // unx
const long long INF=1e15;

int it;
long long ret;
int st[N],ed[N],val[N];
int f[N][22];
long long pf[N],sf[N],dep[N];
vector<ii> ad[N];

void dfs(int u){
    st[u]=++it;
    forinc(i,1,20) f[u][i]=f[f[u][i-1]][i-1];
    forv(v,ad[u]) if(v.fi!=f[u][0]){
        f[v.fi][0]=u;
        dep[v.fi]=dep[u]+v.se;
        dfs(v.fi);
    }
    ed[u]=++it;
}

int anc(int u,int v){
    return st[u]<=st[v] && ed[u]>=ed[v] || !u;
}
int lca(int u,int v){
    if(anc(u,v)) return u;
    if(anc(v,u)) return v;
    fordec(i,20,0) if(!anc(f[u][i],v)) u=f[u][i];
    return f[u][0];
}

void Init(int n,int U[],int V[],int W[]){
    forinc(i,0,n-2){
        int u=U[i]+1, v=V[i]+1, w=W[i];
        ad[u].pb({v,w});
        ad[v].pb({u,w});
    }
    dfs(1);
    forinc(i,1,n) ad[i].clear();
}

void dfs1(int u){
    long long &x=pf[u], &y=sf[u];
    x=val[u]&1 ? 0 : INF, y=val[u]&2 ? 0 : INF;
    forv(v,ad[u]){
        dfs1(v.fi);
        x=min(x,pf[v.fi]+v.se), y=min(y,sf[v.fi]+v.se);
    }
    ret=min(ret,x+y);
}

long long Query(int s,int X[],int t,int Y[]){
    vector<int> node;
    forinc(i,0,s-1) node.push_back(X[i]+1), val[X[i]+1]=1;
    forinc(i,0,t-1) node.push_back(Y[i]+1), val[Y[i]+1]|=2;
    sort(all(node),[](int i,int j){return ii(st[i],ed[i])<ii(st[j],ed[j]);});
    forinc(i,1,node.size()-1) node.push_back(lca(node[i],node[i-1]));
    sort(all(node));
    node.erase(unique(all(node)),node.end());
    sort(all(node),[](int i,int j){return ii(st[i],ed[i])<ii(st[j],ed[j]);});
    stack<int> w;
    forv(v,node){
        while(w.size() && ed[v]>=ed[w.top()]) w.pop();
        if(w.size()){
            ad[w.top()].push_back({v,dep[v]-dep[w.top()]});
        }
        w.push(v);
    }
    ret=INF;
    dfs1(node[0]);
    forv(w,node) val[w]=pf[w]=sf[w]=0, ad[w].clear();
    //gg
    return ret;
}

#ifdef unx
main(){
    #define task "factory"
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);

    int n; cin>>n; int q; cin>>q;
    int x[5010], y[5010], z[5010];
    forinc(i,0,n-2) cin>>x[i]>>y[i]>>z[i];
    Init(n,x,y,z);
    while(q--){ //cerr<<q<<"\n";
        int s,t; cin>>s>>t;
        int S[5010], T[5010];
        forinc(i,0,s-1) cin>>S[i];
        forinc(i,0,t-1) cin>>T[i];
        cout<<Query(s,S,t,T)<<"\n";
    }
}
#endif

Compilation message (stderr)

factories.cpp: In function 'int anc(int, int)':
factories.cpp:53:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return st[u]<=st[v] && ed[u]>=ed[v] || !u;
            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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