oj.uz

답안 #879101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879101 2023-11-26T10:54:11 Z serifefedartar 공장들 (JOI14_factories) C++17
0 / 100
 8000 ms 67932 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 9;
const ll LOGN = 21;
const ll MAXN = 5e5 + 100;

vector<vector<pair<int,int>>> graph;
int marked[MAXN], sz[MAXN], up[LOGN][MAXN], depth[MAXN];
int par[MAXN];
ll depth_dist[MAXN], ans[MAXN];

int get_sz(int node, int parent) {
  sz[node] = 1;
  for (auto u : graph[node]) {
    if (u.f == parent || marked[u.f])
      continue;
    sz[node] += get_sz(u.f, node);
  }
  return sz[node];
}

int find_centro(int node, int parent, int n) {
  for (auto u : graph[node]) {
    if (u.f != parent && !marked[u.f] && sz[u.f] * 2 > sz[node])
      return find_centro(u.f, node, n); 
  }
  return node;
}

void decompose(int node, bool q) {
  int n = get_sz(node, node);
  int centro = find_centro(node, node, n);

  marked[centro] = true;
  if (q)
    par[centro] = -1;
  else
    par[centro] = node;

  for (auto u : graph[centro]) {
    if (!marked[u.f])
      decompose(u.f, false);
  }
}

void dfs(int node, int parent) {
  for (auto u : graph[node]) {
    if (u.f == parent)
      continue;
    depth[u.f] = depth[node] + 1;
    depth_dist[u.f] = depth_dist[node] + u.s;
    up[0][u.f] = node;
    for (int i = 1; i < LOGN; i++)
      up[i][u.f] = up[i-1][up[i-1][u.f]];
    dfs(u.f, node);
  }
}

int find(int node, int k) {
  for (int i = 0; i < LOGN; i++) {
    if ((1<<i) & k)
      node = up[i][node];
  }
  return node;
}

int lca(int a, int b) {
  if (depth[b] > depth[a])
    swap(a, b);
  a = find(a, depth[a] - depth[b]);
  if (a == b)
    return a;

  for (int i = LOGN - 1; i >= 0; i--) {
    if (up[i][a] != up[i][b]) {
      a = up[i][a];
      b = up[i][b];
    }
  }
  return up[0][a];
}

ll dist(int a, int b) {
  return depth_dist[a] + depth_dist[b] - 2 * depth_dist[lca(a, b)];
}

void Init(int N, int A[], int B[], int D[]) {
  graph = vector<vector<pair<int,int>>>(N+1, vector<pair<int,int>>());
  for (int i = 0; i < N-1; i++) {
    graph[A[i] + 1].push_back({B[i] + 1, D[i]});
    graph[B[i] + 1].push_back({A[i] + 1, D[i]});
  }
  dfs(1, 1);
  decompose(1, true);

  for (int i = 0; i < MAXN; i++)
    ans[i] = 1e15;
}

void add(int node) {
  int now = node;
  while (now != -1) {
    ans[now] = min(ans[now], dist(now, node));
    now = par[now];
  }
}

void remove(int node) {
  while (node != -1) {
    ans[node] = 1e15;
    node = par[node];
  }
}

ll qry(int node) {
  int now = node;
  ll res = 1e15;
  while (now != -1) {
    res = min(res, dist(now, node) + ans[now]);
    now = par[now];
  }
  return res;
}

ll Query(int S, int X[], int T, int Y[]) {
  for (int i = 0; i < S; i++)
    add(X[i] + 1);

  ll mn = 1e16;
  for (int i = 0; i < T; i++)
    mn = min(mn, qry(Y[i] + 1));

  for (int i = 0; i < S; i++)
    remove(X[i] + 1);
  return mn;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8061 ms 67932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8042 ms 67932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 8061 ms 67932 KB Time limit exceeded
2 Halted 0 ms 0 KB -