Submission #335921

#	Time	Username	Problem	Language	Result	Execution time	Memory
335921		Thistle	Factories (JOI14_factories)	C++14	15 / 100	8061 ms	129224 KiB

factories

#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "factories.h"


using namespace std;
using ll=long long;
using H=pair<ll, ll>;
#define fs first
#define sc second
#define rng(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) rng(i,0,n)
#define vec vector
#define pb push_back
template<typename T>
void chmax(T &a,T b){a=max(a,b);}
template<typename T>
void chmin(T &a,T b){a=min(a,b);}

constexpr ll inf=1e17;

int n;
ll dpt[600000],dpt2[600000];
int pa[600000][20];
vec<bool>dead;
int root;
vec<int>tree[600000];
int par[600000];
vec<H>e[600000];
ll lca(int x,int y){
  if(dpt2[x]<dpt2[y]) swap(x,y);
  ll ret=0;
  rep(i,20)if((1<<i)&(dpt2[x]-dpt2[y])){
    ret+=dpt[x]-dpt[pa[x][i]];
    x=pa[x][i];
  }
  for(int i=19;i>=0;i--){
    if(pa[x][i]!=pa[y][i]){
      ret+=dpt[x]-dpt[pa[x][i]];
      ret+=dpt[y]-dpt[pa[y][i]];
      x=pa[x][i];y=pa[y][i];
    }
  }
  if(x!=y){
    ret+=dpt[x]-dpt[pa[x][0]];
    ret+=dpt[y]-dpt[pa[y][0]];
  }
  return ret;
}
int octr(int x){
  static int sz[600000];
  auto rec=[&](int pos,int p, auto& rec)->void{
    sz[pos]=1;
    for(auto g:e[pos]){
      if(g.fs==p||dead[g.fs]) continue;
      rec(g.fs,pos,rec);
      sz[pos]+=sz[g.fs];
    }
  };
  rec(x,-1,rec);
  int N=sz[x];
  auto dfs=[&](int pos,int p,auto& dfs)->int{
    for(auto g:e[pos]){
      if(g.fs==p||dead[g.fs]) continue;
      if(sz[g.fs]>N/2) return dfs(g.fs,pos,dfs);
    }
    return pos;
  };
  return dfs(x,-1,dfs);
}
int build(int x){
  int c=octr(x);
  dead[c]=1;
  if(root==-1) root=c;
  for(auto g:e[c]){
    if(dead[g.fs])continue;
    int k=build(g.fs);
    tree[c].pb(k);
    par[k]=c;
  }
  return c;
}

void Init(int N, int A[], int B[], int D[]) {
  n=N;
  rep(i,n-1){
    e[A[i]].pb(H{B[i],D[i]});
    e[B[i]].pb(H{A[i],D[i]});
  }
  auto dfs=[&](int x,int p,ll d,int d2,auto& dfs)->void{
    dpt[x]=d,pa[x][0]=p,dpt2[x]=d2;
    for(auto g:e[x]){
      if(g.fs==p) continue;
      dfs(g.fs, x, d+g.sc,d2+1, dfs);
    }
  };
  dfs(0,-1,0,0,dfs);
  rep(i,n)rng(j,1,20) pa[i][j]=-1;
  rep(j,19)rep(i,n){
    if(pa[i][j]==-1) pa[i][j+1]=-1;
    else pa[i][j+1]=pa[pa[i][j]][j];
  }
  root=-1;
  dead.assign(n,false);
  build(0);
}

long long Query(int S, int X[], int T, int Y[]) {
  ll ans=inf;
  map<int, ll>mp;
  rep(i,S){
    int t=X[i]; mp[t]=0;
    do{
      t=par[t];
      if(mp.find(t)==mp.end()) mp[t]=lca(t,X[i]);
      else chmin(mp[t],lca(t,X[i]));
    }while(t!=root);
  }
  rep(i,T){
    int t=Y[i];
    if(mp.find(t)!=mp.end()) chmin(ans,mp[t]);
    do{
      t=par[t];
      if(mp.find(t)!=mp.end()) chmin(ans,lca(Y[i],t)+mp[t]);
    }while(t!=root);
  }
  return ans;
}

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