제출 #319693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319693		tushar_2658	공장들 (JOI14_factories)	C++14	0 / 100	87 ms	114276 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 500005;
using ll = long long;

vector<pair<int, int>> edges[maxn];
int n;
ll dis[maxn], sparse[maxn][20];
int depth[maxn];

void dfs(int x, int p, ll c){
  dis[x] = c;
  depth[x] = depth[p] + 1;
  sparse[x][0] = p;
  for(auto i : edges[x]){
    if(i.first != p){
      dfs(i.first, x, c + i.second);
    }
  }
} 

void build_lca(){
  for(int j = 1; j < 20; ++j){
    for(int i = 1; i <= n; ++i){
      if(sparse[i][j - 1] != -1){
        sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
      }
    }
  }
}

int LCA(int x, int y){
  if(depth[x] < depth[y])swap(x, y);
  for(int i = 19; i >= 0; --i){
    if(depth[x] - (1 << i) >= depth[y]){
      x = sparse[x][i];
    }
  }
  if(x == y)return x;
  for(int i = 19; i >= 0; --i){
    if(sparse[x][i] != sparse[y][i] && sparse[x][i] != -1 && sparse[y][i] != -1){
      x = sparse[x][i];
      y = sparse[y][i];
    }
  }
  return sparse[x][0];
}

ll DIS(int x, int y){
  return dis[x] + dis[y] - (2 * dis[LCA(x, y)]);
}

multiset<int> G[maxn];
int sub[maxn], par[maxn];

void rem(int x, int y){
  G[x].erase(y);
  G[y].erase(x);
}

void dfs(int x, int p){
  sub[x] = 1;
  for(auto i : G[x]){
    if(i != p){
      dfs(i, x);
      sub[x] += sub[i];
    }
  }
}

int find_centroid(int x, int p, int range){
  for(auto i : G[x]){
    if(i != p){
      if(sub[i] > range)return find_centroid(i, x, range);
    }
  }return x;
}

void build(int x, int p){
  dfs(x, p);
  int c = find_centroid(x, 0, sub[x] / 2);
  par[c] = p;
  vector<int> v;
  copy(G[c].begin(), G[c].end(), back_inserter(v));
  for(auto i : v){
    rem(c, i);
    build(i, c);
  }
}

vector<int> vis(n + 1);
vector<int> changed;
ll mn[maxn];

void upd(int x){
  int cur = x;
  while(cur != 0){
    if(!vis[cur]){
      changed.push_back(cur);
      vis[cur] = 1;
    }
    mn[cur] = min(mn[cur], DIS(x, cur));
    cur = par[cur];
  }
}

ll query(int x){
  ll ret = mn[x];
  int cur = x;
  while(cur != 0){
    ret = min(ret, mn[cur] + DIS(x, cur));
    cur = par[cur];
  }
  return ret;
}

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  for(int i = 0; i < N - 1; ++i){
    edges[A[i] + 1].push_back({B[i] + 1, D[i]});
    edges[B[i] + 1].push_back({A[i] + 1, D[i]});
    G[A[i] + 1].insert(B[i] + 1);
    G[B[i] + 1].insert(A[i] + 1);
  }
  memset(sparse, -1, sizeof sparse);
  dfs(1, 1, 0);
  build_lca();
  build(1, 0);
  for(int i = 0; i <= N; ++i){
    mn[i] = 1e18;
  }
}

long long Query(int S, int X[], int T, int Y[]) {
  for(int i = 0; i < S; ++i){
    upd(X[i] + 1);
  }
  ll ans = 1e18;
  for(int i = 0; i < T; ++i){
    ans = min(ans, query(Y[i] + 1));
  }
  for(auto i : changed){
    vis[i] = 0;
    mn[i] = 1e18;
  }
  changed.clear();
  return ans;
}

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