Submission #915264

#	Time	Username	Problem	Language	Result	Execution time	Memory
915264		uped	Factories (JOI14_factories)	C++14	100 / 100	5562 ms	374464 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];
vector<pair<ll, int>> 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 r, int n, ll s, int p = -1) {
  dist[n].emplace_back(s, r);
  for (auto& [x, w] : adj[n]) {
    if (removed[x] || x == p) continue;
    dfs(r, 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].emplace_back(0, c);
  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) {
    for (auto& [d, n] : dist[X[i]]) {
      best[n] = min(best[n], d);
    }
  }
  ll ans = LLONG_MAX;
  for (int i = 0; i < T; ++i) {
    
    for (auto& [d, n] : dist[Y[i]]) {
      if (best[n] == INF) continue;
      ans = min(ans, best[n] + d);
    }
  }
  for (int i = 0; i < S; ++i) {
    for (auto& [_, n] : dist[X[i]]) {
      best[n] = INF;
    }
  }

  return ans;
}

Compilation message (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]) {
      |              ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:75:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for (auto& [d, n] : dist[X[i]]) {
      |                ^
factories.cpp:82:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |     for (auto& [d, n] : dist[Y[i]]) {
      |                ^
factories.cpp:88:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   88 |     for (auto& [_, n] : dist[X[i]]) {
      |                ^

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