제출 #480431

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

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 500123;
const int LOG = 25;

int par[MAX][LOG];
int dep[MAX];
long long path[MAX];
vector<pair<int, int>> g[MAX];

void Dfs(int u, int p) {
  par[u][0] = p;
  for (int i = 1; i < LOG; i++) {
    par[u][i] = par[par[u][i - 1]][i - 1];
  }
  for (auto e : g[u]) {
    int v = e.first;
    int w = e.second;
    if (v == p) {
      continue;
    }
    dep[v] = dep[u] + 1;
    path[v] = path[u] + w;
    Dfs(v, u);
  }
}

int Lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = LOG - 1; i >= 0; i--) {
    if (dep[par[u][i]] >= dep[v]) {
      u = par[u][i];
    }
  }
  for (int i = LOG - 1; i >= 0; i--) {
    if (par[u][i] != par[v][i]) {
      u = par[u][i];
      v = par[v][i];
    }
  }
  return (u == v ? u : par[u][0]);
}

long long dist(int u, int v) {
  return path[u] + path[v] - 2 * path[Lca(u, v)];
}

int sz[MAX];
bool was[MAX];
vector<int> up[MAX];

void DfsSz(int u, int p) {
  sz[u] = 1;
  for (auto e : g[u]) {
    int v = e.first;
    if (!was[v] && v != p) {
      DfsSz(v, u);
      sz[u] += sz[v];
    }
  }
}

int FindCen(int u, int p, int n) {
  for (auto e : g[u]) {
    int v = e.first;
    if (!was[v] && v != p && sz[v] * 2 >= n) {
      return FindCen(v, u, n);
    }
  }
  return u;
}

int Who(int u) {
  DfsSz(u, u);
  return FindCen(u, u, sz[u]);
}

void Update(int u, int p, int st) {
  up[u].push_back(st);
  for (auto e : g[u]) {
    int v = e.first;
    if (v == p || was[v]) {
      continue;
    }
    Update(v, u, st);
  }
}

void Find(int u) {
  u = Who(u);
  was[u] = true;
  Update(u, u, u);
  for (auto e : g[u]) {
    int v = e.first;
    if (!was[v]) {
      Find(v);
    }
  }
}

void Init(int N, int A[], int B[], int D[]) {
  for (int i = 0; i < N - 1; i++) {
    ++A[i]; ++B[i];
    g[A[i]].emplace_back(B[i], D[i]);
    g[B[i]].emplace_back(A[i], D[i]);
  }
  Dfs(1, 0);
  Find(1);
}

int lst[MAX];
int qId;
long long qdist[MAX];

long long Query(int S, int X[], int T, int Y[]) {
  qId++;
  for (int i = 0; i < S; i++) {
    for (int j : up[X[i] + 1]) {
      lst[j] = qId;
      qdist[j] = dist(X[i] + 1, j);
    }
  }
  long long ans = 1e18;
  /*for (int i = 0; i < T; i++) {
    for (int j : up[Y[i] + 1]) {
      if (lst[j] == qId) {
        ans = min(ans, qdist[j] + dist(Y[i] + 1, j));
      }
    }
  }*/
  for (int i = 0; i < S; i++) {
    for (int j = 0; j < T; j++) {
      ans = min(ans, dist(X[i] + 1, Y[j] + 1));
    }
  }
  return ans;
}

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