Submission #1081840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081840		Malix	Factories (JOI14_factories)	C++14	100 / 100	2635 ms	296544 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,ll> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int n,stv=0,env=0,k;
vector<pii> a;
vi st,en,sz,vis,par;
vector<ll> dist,d;
vii p,b;
vector<vector<ll>> dst;

void dfs(int x){
  st[x]=stv++;
  for(auto u:a[x])if(p[x][0]!=u.F){
    p[u.F][0]=x;
    dist[u.F]=dist[x]+u.S;
    dfs(u.F);
    sz[x]+=sz[u.F];
  }
  en[x]=env++;
}

bool ances(int x,int y){
  if(y==-1)return 1;
  if(st[x]>=st[y]&&en[x]<=en[y])return 1;
  return 0;
}

ll distance(int x,int y){
  if(ances(x,y)||ances(y,x))return abs(dist[x]-dist[y]);
  int z=y;
  for(int i=k-1;i>=0;i--)if(!ances(x,p[y][i]))y=p[y][i];
  y=p[y][0];
  return dist[x]+dist[z]-2*dist[y];
}

int centroid(int x,int y){
  for(auto u:a[x])if(vis[u.F]==0&&sz[u.F]>y/2){
    sz[x]-=sz[u.F];
    sz[u.F]=y;
    return centroid(u.F,y);
  }
  return x;
}

void decompose(int x){
  for(auto u:a[x])if(!vis[u.F]){
    int y=centroid(u.F,sz[u.F]);
    b[x].PB(y);
    vis[y]=1;
    par[y]=x;
    decompose(y);
  }
}

void Init(int N, int A[], int B[], int D[]) {
  n=N;
  k=log2(n)+1;
  a.resize(n);p.resize(n,vi(k,-1));sz.resize(n,1);dist.resize(n,0);
  REP(i,0,n-1){
    a[A[i]].PB({B[i],(ll)D[i]});
    a[B[i]].PB({A[i],(ll)D[i]});
  }
  st.resize(n);en.resize(n);
  dfs(0);
  REP(j,1,k)REP(i,0,n)if(p[i][j-1]!=-1)p[i][j]=p[p[i][j-1]][j-1];
  vis.resize(n,0);b.resize(n);par.resize(n,-1);
  int x=centroid(0,n);
  vis[x]=1;
  decompose(x);
  dst.resize(n,vector<ll>(k));d.resize(n,INF);
  REP(i,0,n){
    int r=i;
    int ps=0;
    while(r!=-1){
      dst[i][ps]=distance(i,r);
      r=par[r];
      ps++;
    }
  }
}

long long Query(int s, int X[], int t, int Y[]) {
  ll ans=INF;
  REP(i,0,s){
    int r=X[i];
    while(r!=-1){
      d[r]=INF;
      r=par[r];
    }
  }
  REP(i,0,t){
    int r=Y[i];
    while(r!=-1){
      d[r]=INF;
      r=par[r];
    }
  }
  REP(i,0,s){
    int r=X[i];
    int ps=0;
    while(r!=-1){
      d[r]=min(d[r],dst[X[i]][ps]);
      r=par[r];ps++;
    }
  }
  REP(i,0,t){
    int r=Y[i];
    int ps=0;
    while(r!=-1){
      if(d[r]!=INF)ans=min(ans,d[r]+dst[Y[i]][ps]);
      r=par[r];ps++;
    }
  }
  return ans;
}

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