Submission #1230891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230891		long290429	Factories (JOI14_factories)	C++20	0 / 100	2148 ms	111696 KiB

factories

#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int tin[maxn],tout[maxn];
int dep[maxn],dtr[maxn];
vector<pair<int,int>> adj[maxn];
int tt,lg;
vector<vector<int>> up;
void dfs(int u,int par) {
  tin[u]=++tt;
  up[u][0]=par;
  for(int i=1;i<=lg;++i) {
    if(up[u][i-1]!=-1) {
      up[u][i]=up[up[u][i-1]][i-1];
    }
    else break;
  }
  for(pair<int,int> p:adj[u]) {
    int v=p.first,w=p.second;
    if(v==par) continue;
    dep[v]=dep[u]+1;
    dtr[v]=dtr[u]+w;
    dfs(v,u);
  }
  tout[u]=tt;
}
int lca(int u,int v) {
  if(dep[u]<dep[v]) swap(u,v);
  int k=dep[u]-dep[v];
  for(int i=0;k>0;++i) {
    if(k&1) {
      u=up[u][i];
    }
    k>>=1;
  }
  if(u==v) return u;
  for(int i=lg;i>=0;--i) {
    if(up[u][i]!=-1&&up[v][i]!=-1&&up[u][i]!=up[v][i]) {
      u=up[u][i];
      v=up[v][i];
    }
  }
  return up[u][0];
}
long long solve(int a[],int n,int b[],int m) {
  vector<pair<int,int>> c(n+m);
  for(int i=0;i<n+m;++i) {
    if(i<n) c[i]=make_pair(tin[a[i]],a[i]);
    else c[i]=make_pair(tin[b[i-n]],b[i-n]);
  }
  sort(c.begin(),c.end());
  int sz=c.size();
  for(int i=1;i<sz;++i) {
    int anc=lca(c[i].second,c[i-1].second);
    c.push_back({tin[anc],anc});
  }
  sort(c.begin(),c.end());
  c.erase(unique(c.begin(),c.end()),c.end());
  sz=c.size();
  unordered_map<int,int> idx;
  idx.reserve(sz);
  for(int i=0;i<sz;++i) {
    idx[c[i].second]=i;
  }
  vector<int> st;
  vector<vector<pair<int,int>>> vt(sz);
  for(pair<int,int> p:c){
    int u=p.second;
    int id=idx[u];
    while(!st.empty()&&!(tin[c[st.back()].second]<=tin[u]&&tout[u]<=tout[c[st.back()].second])) {
      st.pop_back();
    }
    if(!st.empty()) {
      int v=st.back();
      int node=c[v].second;
      int len=dtr[u]-dtr[node];
      vt[v].push_back({id,len});
      vt[id].push_back({v,len});
    }
    st.push_back(id);
  }
  long long inf=LLONG_MAX/4,ans;
  ans=inf;
  vector<long long> da(sz,inf),db(sz,inf);
  for(int i=0;i<n;++i) {
    da[idx[a[i]]]=0;
  }
  for(int i=0;i<m;++i) {
    db[idx[b[i]]]=0;
  }
  function<void(int,int)> dfs1=[&](int u,int par) {
    for(pair<int,int> p:vt[u]) {
      int v=p.first,w=p.second;
      if(v==par) continue;
      dfs1(v,u);
      da[u]=min(da[u],da[v]+w);
      db[u]=min(db[u],db[v]+w);
    }
    ans=min(ans,da[u]+db[u]);
  };
  dfs1(st[0],-1);
  function<void(int,int)> dfs2=[&](int u,int par) {
    for(pair<int,int> p:vt[u]) {
      int v=p.first,w=p.second;
      if(v==par) continue;
      da[v]=min(da[v],da[u]+w);
      db[v]=min(db[v],db[u]+w);
      ans=min(ans,da[v]+db[v]);
      dfs2(v,u);
    }
  };
  dfs2(st[0],-1);
  return ans;
}
void Init(int n,int u[],int v[],int w[]) {
  for(int i=0;i<n;++i) adj[i].clear();
  for(int i=0;i<n-1;++i) {
    adj[u[i]].push_back({v[i],w[i]});
    adj[v[i]].push_back({u[i],w[i]});
  }
  tt=0;
  dep[0]=0;
  dtr[0]=0;
  lg=floor(log2(n));
  up.assign(n,vector<int>(lg+1,-1));
  dfs(0,-1);
}
long long Query(int s,int x[],int t,int y[]) {
  return solve(x,s,y,t);
}

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