oj.uz

답안 #335924

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
335924 2020-12-14T10:00:18 Z Thistle 공장들 (JOI14_factories) C++14
15 / 100
 8000 ms 129292 KB 
#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;
  unordered_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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 29036 KB Output is correct
2 Correct 1980 ms 37612 KB Output is correct
3 Correct 3284 ms 37868 KB Output is correct
4 Correct 2481 ms 37836 KB Output is correct
5 Correct 4204 ms 38144 KB Output is correct
6 Correct 608 ms 37484 KB Output is correct
7 Correct 3266 ms 37612 KB Output is correct
8 Correct 3300 ms 37644 KB Output is correct
9 Correct 4206 ms 38252 KB Output is correct
10 Correct 605 ms 37612 KB Output is correct
11 Correct 3253 ms 38000 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 28780 KB Output is correct
2 Correct 4867 ms 125296 KB Output is correct
3 Execution timed out 8073 ms 129292 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 29036 KB Output is correct
2 Correct 1980 ms 37612 KB Output is correct
3 Correct 3284 ms 37868 KB Output is correct
4 Correct 2481 ms 37836 KB Output is correct
5 Correct 4204 ms 38144 KB Output is correct
6 Correct 608 ms 37484 KB Output is correct
7 Correct 3266 ms 37612 KB Output is correct
8 Correct 3300 ms 37644 KB Output is correct
9 Correct 4206 ms 38252 KB Output is correct
10 Correct 605 ms 37612 KB Output is correct
11 Correct 3253 ms 38000 KB Output is correct
12 Correct 25 ms 28780 KB Output is correct
13 Correct 4867 ms 125296 KB Output is correct
14 Execution timed out 8073 ms 129292 KB Time limit exceeded
15 Halted 0 ms 0 KB -