oj.uz

Submission #915232

# Submission time Handle Problem Language Result Execution time Memory
915232 2024-01-23T14:33:37 Z uped Factories (JOI14_factories) C++14
15 / 100
 8000 ms 425084 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];
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); 
  }
}

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]);
  }
  decompose();
}

long long Query(int S, int X[], int T, int Y[]) {
  map<int, ll> m;
  for (int i = 0; i < S; ++i) {
    int cur = X[i];
    while (cur != -1) {
      if (!m.count(cur)) {
        m[cur] = dist[cur][X[i]];
      } else {
        m[cur] = min(m[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 (m.count(cur)) {
        ans = min(ans, m[cur] + dist[cur][Y[i]]);
      }
      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 47 ms 58456 KB Output is correct
2 Correct 2723 ms 74408 KB Output is correct
3 Correct 3779 ms 74896 KB Output is correct
4 Correct 3108 ms 75096 KB Output is correct
5 Correct 5008 ms 75868 KB Output is correct
6 Correct 608 ms 72528 KB Output is correct
7 Correct 3633 ms 74852 KB Output is correct
8 Correct 3759 ms 75016 KB Output is correct
9 Correct 5006 ms 75864 KB Output is correct
10 Correct 599 ms 72552 KB Output is correct
11 Correct 3674 ms 74856 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 58204 KB Output is correct
2 Execution timed out 8026 ms 425084 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 58456 KB Output is correct
2 Correct 2723 ms 74408 KB Output is correct
3 Correct 3779 ms 74896 KB Output is correct
4 Correct 3108 ms 75096 KB Output is correct
5 Correct 5008 ms 75868 KB Output is correct
6 Correct 608 ms 72528 KB Output is correct
7 Correct 3633 ms 74852 KB Output is correct
8 Correct 3759 ms 75016 KB Output is correct
9 Correct 5006 ms 75864 KB Output is correct
10 Correct 599 ms 72552 KB Output is correct
11 Correct 3674 ms 74856 KB Output is correct
12 Correct 18 ms 58204 KB Output is correct
13 Execution timed out 8026 ms 425084 KB Time limit exceeded
14 Halted 0 ms 0 KB -