제출 #1281251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281251		nicolo_010	공장들 (JOI14_factories)	C++20	100 / 100	2410 ms	341204 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
using pii = pair<int, ll>;

vector<bool> removed;
vector<vector<pii>> cd;
vector<vector<pii>> adj;
vector<int> sz;
vector<ll> dist;

int dfs(int n, int p=-1) {
  sz[n] = 1;
  for (auto x : adj[n]) {
    if (x.first==p || removed[x.first]) continue;
    sz[n] += dfs(x.first, n);
  }
  return sz[n];
}

int centroid(int u, int n, int p=-1) {
  for (auto x : adj[u]) {
    if (x.first == p || removed[x.first]) continue;
    if (sz[x.first]*2 > n) return centroid(x.first, n, u);
  }
  return u;
}

void upd(int n, int c, ll dis, int p=-1) {
  cd[n].push_back({c, dis});
  for (auto x : adj[n]) {
    if (x.first == p || removed[x.first]) continue;
    upd(x.first, c, dis+x.second, n);
  }
}

void build(int u) {
  int n=dfs(u);
  int c = centroid(u, n);
  removed[c] = true;
  upd(c, c, 0);
  for (auto x : adj[c]) {
    if (removed[x.first]) continue;
    build(x.first);
  }
}

void Init(int N, int A[], int B[], int D[]) {
  adj.assign(N, {});
  cd.assign(N, {});
  removed.assign(N, false);
  sz.assign(N, 0);
  for (int i=0; i<N-1; i++) {
    int a = A[i];
    int b = B[i];
    adj[a].push_back({b, D[i]});
    adj[b].push_back({a, D[i]});
  }
  build(0);
  dist.assign(N, 1e18);
}

long long Query(int S, int X[], int T, int Y[]) {
  for (int i=0;i<T; i++) {
    for (auto x : cd[Y[i]]) {
      dist[x.first] = 1e18;
    }
  }
  for (int i=0; i<S; i++) {
    for (auto x : cd[X[i]]) {
      dist[x.first] = min(dist[x.first], x.second);
    }
  }
  ll ans = 1e18;
  for (int i=0; i<T; i++) {
    for (auto x : cd[Y[i]]) {
      ans = min(ans, dist[x.first]+x.second);
    }
  }
  return ans;
}

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