제출 #915252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915252		uped	Factories (JOI14_factories)	C++14	15 / 100	6001 ms	524288 KiB

factories

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

#define DEBUG(x) cout << #x << ": " << x << '\n';
using namespace std;
using ll = long long;


const int MAXN = 5e5;

vector<pair<int, ll>> adj[MAXN];
int sz[MAXN];
int parent[MAXN];
bool removed[MAXN];
unordered_map<int, ll> dist[MAXN];

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

int get_c(int d, int n, int p = -1) {
  for (auto& [x, _] : adj[n]) {
    if (removed[x] || x == p) continue;
    if (sz[x] > d) return get_c(d, x, n);
  }
  return n;
}

void dfs(int o, int n, ll s, int p = -1) {
  dist[o][n] = s;
  for (auto& [x, w] : adj[n]) {
    if (removed[x] || x == p) continue;
    dfs(o, x, s + w, n);
  }
}

void decompose(int n = 0, int p = -1) {
  int c = get_c(get_sz(n) / 2, n);
  removed[c] = true;
  parent[c] = p;
  dist[c][c] = 0ll;
  for (auto& [x, w] : adj[c]) {
    if (removed[x]) continue;
    dfs(c, x, w, c);
  }

  for (auto& [x, _] : adj[c]) {
    if (removed[x]) continue;
    decompose(x, c); 
  }
}

const ll INF = 1e18;
ll best[MAXN];

void Init(int N, int A[], int B[], int D[]) {
  for (int i = 0; i < N - 1; ++i) {
    adj[A[i]].emplace_back(B[i], D[i]);
    adj[B[i]].emplace_back(A[i], D[i]);
  }
  for (int i =0; i < MAXN; ++i) {
    best[i] = INF;
  } 
  decompose();
}


long long Query(int S, int X[], int T, int Y[]) {
  for (int i = 0; i < S; ++i) {
    int cur = X[i];
    while (cur != -1) {
      best[cur] = min(best[cur], dist[cur][X[i]]);
      cur = parent[cur];
    }

  }
  ll ans = LLONG_MAX;
  for (int i = 0; i < T; ++i) {
    int cur = Y[i];
    while (cur != -1) {
      if (best[cur] != INF) ans = min(ans, best[cur] + dist[cur][Y[i]]);
      cur = parent[cur];
    }
  }
  for (int i = 0; i < S; ++i) {
    int cur = X[i];
    while (cur != -1) {
      best[cur] = INF;
      cur = parent[cur];
    }
  }

  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'int get_sz(int, int)':
factories.cpp:19:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |   for (auto& [x, _] : adj[n]) {
      |              ^
factories.cpp: In function 'int get_c(int, int, int)':
factories.cpp:27:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |   for (auto& [x, _] : adj[n]) {
      |              ^
factories.cpp: In function 'void dfs(int, int, ll, int)':
factories.cpp:36:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |   for (auto& [x, w] : adj[n]) {
      |              ^
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:47:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |   for (auto& [x, w] : adj[c]) {
      |              ^
factories.cpp:52:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |   for (auto& [x, _] : adj[c]) {
      |              ^

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