Submission #335951

#	Time	Username	Problem	Language	Result	Execution time	Memory
335951		Thistle	Factories (JOI14_factories)	C++14	15 / 100	8068 ms	233588 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 siz(a) (a.size())
#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];
vec<bool>dead;
int root;
vec<int>tree[600000];
int par[600000];
vec<H>e[600000];
vec<int>eul,out;
int spt[1300000][20];
int lgt[1300000];
int id[1300000];
ll lca2(int x,int y){
  ll ret=0;
  x=id[x],y=id[y];
  if(x>y) swap(x,y);
  int k=lgt[y-x];
  x=spt[x][k];
  y=spt[y-(1<<k)+1][k];
  if(eul[spt[x][0]]<eul[spt[y][0]]) return out[spt[x][0]];
  else return out[spt[y][0]];
}
ll lca(int x,int y){
  int k=lca2(x,y);
  return dpt[x]+dpt[y]-2*dpt[k];
}
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]=p,dpt2[x]=d2;
    for(auto g:e[x]){
      if(g.fs==p) continue;
      eul.pb(dpt2[x]);out.pb(x);
      dfs(g.fs, x, d+g.sc,d2+1, dfs);
    }
    id[x]=siz(eul);
    eul.pb(dpt2[x]);out.pb(x);
  };
  dfs(0,-1,0,0,dfs);


  rep(i,siz(eul)) spt[i][0]=i;
  rng(i,2,siz(eul)+2) lgt[i]=lgt[i>>1]+1;

  rep(i,19)for(int j=0;j+(1<<i)<=siz(eul);j++){
    int idx1=spt[j][i],idx2=spt[j+(1<<i)][i];
    if(eul[idx1]<eul[idx2]) spt[j][i+1]=idx1;
    else spt[j][i+1]=idx2;
  }


  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;
}

Compilation message (stderr)

factories.cpp: In function 'll lca2(int, int)':
factories.cpp:37:6: warning: unused variable 'ret' [-Wunused-variable]
   37 |   ll ret=0;
      |      ^~~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:12:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rng(i,a,b) for(ll i=(a);i<(b);i++)
      |                                  ^
factories.cpp:13:18: note: in expansion of macro 'rng'
   13 | #define rep(i,n) rng(i,0,n)
      |                  ^~~
factories.cpp:103:3: note: in expansion of macro 'rep'
  103 |   rep(i,siz(eul)) spt[i][0]=i;
      |   ^~~
factories.cpp:12:34: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 | #define rng(i,a,b) for(ll i=(a);i<(b);i++)
      |                                  ^
factories.cpp:104:3: note: in expansion of macro 'rng'
  104 |   rng(i,2,siz(eul)+2) lgt[i]=lgt[i>>1]+1;
      |   ^~~
factories.cpp:106:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   rep(i,19)for(int j=0;j+(1<<i)<=siz(eul);j++){
      |                                ^

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