제출 #566649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566649		SSRS	공장들 (JOI14_factories)	C++14	18 / 100	8028 ms	99436 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const long long INF = 1000000000000000;
struct heavy_light_decomposition{
  vector<int> p, sz, in, next;
  vector<long long> d;
  heavy_light_decomposition(){
  }
  heavy_light_decomposition(vector<int> &p, vector<vector<int>> &c, vector<long long> &d): p(p), d(d){
    int N = p.size();
    sz = vector<int>(N, 1);
    dfs1(c);
    in = vector<int>(N);
    next = vector<int>(N, 0);
    int t = 0;
    dfs2(c, t);
  }
  void dfs1(vector<vector<int>> &c, int v = 0){
    for (int &w : c[v]){
      dfs1(c, w);
      sz[v] += sz[w];
      if (sz[w] > sz[c[v][0]]){
        swap(w, c[v][0]);
      }
    }
  }
  void dfs2(vector<vector<int>> &c, int &t, int v = 0){
    in[v] = t;
    t++;
    for (int w : c[v]){
      if (w == c[v][0]){
        next[w] = next[v];
      } else {
        next[w] = w;
      }
      dfs2(c, t, w);
    }
  }
  int lca(int u, int v){
    while (true){
      if (in[u] > in[v]){
        swap(u, v);
      }
      if (next[u] == next[v]){
        return u;
      }
      v = p[next[v]];
    }
  }
  long long dist(int u, int v){
    return d[u] + d[v] - 2 * d[lca(u, v)];
  }
};
heavy_light_decomposition HLD;
void Init(int N, int A[], int B[], int D[]){
  vector<vector<pair<int, int>>> E(N);
  for (int i = 0; i < N - 1; i++){
    E[A[i]].push_back(make_pair(D[i], B[i]));
    E[B[i]].push_back(make_pair(D[i], A[i]));
  }
  vector<int> p(N, -1);
  vector<vector<int>> c(N);
  vector<long long> d(N, 0);
  queue<int> Q;
  Q.push(0);
  while (!Q.empty()){
    int v = Q.front();
    Q.pop();
    for (auto P : E[v]){
      int w = P.second;
      if (w != p[v]){
        p[w] = v;
        c[v].push_back(w);
        d[w] = d[v] + P.first;
        Q.push(w);
      }
    }
  }
  HLD = heavy_light_decomposition(p, c, d);
}
long long Query(int S, int X[], int T, int Y[]){
  long long ans = INF;
  for (int i = 0; i < S; i++){
    for (int j = 0; j < T; j++){
      ans = min(ans, HLD.dist(X[i], Y[j]));
    }
  }
  return ans;
}

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