oj.uz

Submission #915252

# Submission time Handle Problem Language Result Execution time Memory
915252 2024-01-23T15:00:32 Z uped Factories (JOI14_factories) C++14
15 / 100
 6001 ms 524288 KB 
#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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64604 KB Output is correct
2 Correct 469 ms 79824 KB Output is correct
3 Correct 516 ms 80604 KB Output is correct
4 Correct 443 ms 80468 KB Output is correct
5 Correct 588 ms 80976 KB Output is correct
6 Correct 208 ms 78860 KB Output is correct
7 Correct 499 ms 80436 KB Output is correct
8 Correct 533 ms 80636 KB Output is correct
9 Correct 644 ms 81240 KB Output is correct
10 Correct 197 ms 78912 KB Output is correct
11 Correct 507 ms 80520 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 64348 KB Output is correct
2 Correct 4086 ms 377920 KB Output is correct
3 Correct 6001 ms 488232 KB Output is correct
4 Correct 1045 ms 204696 KB Output is correct
5 Runtime error 3729 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 64604 KB Output is correct
2 Correct 469 ms 79824 KB Output is correct
3 Correct 516 ms 80604 KB Output is correct
4 Correct 443 ms 80468 KB Output is correct
5 Correct 588 ms 80976 KB Output is correct
6 Correct 208 ms 78860 KB Output is correct
7 Correct 499 ms 80436 KB Output is correct
8 Correct 533 ms 80636 KB Output is correct
9 Correct 644 ms 81240 KB Output is correct
10 Correct 197 ms 78912 KB Output is correct
11 Correct 507 ms 80520 KB Output is correct
12 Correct 19 ms 64348 KB Output is correct
13 Correct 4086 ms 377920 KB Output is correct
14 Correct 6001 ms 488232 KB Output is correct
15 Correct 1045 ms 204696 KB Output is correct
16 Runtime error 3729 ms 524288 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -