oj.uz

Submission #915238

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

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[]) {
  unordered_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 31 ms 62296 KB Output is correct
2 Correct 832 ms 78144 KB Output is correct
3 Correct 1151 ms 78640 KB Output is correct
4 Correct 927 ms 78764 KB Output is correct
5 Correct 1282 ms 79208 KB Output is correct
6 Correct 320 ms 76936 KB Output is correct
7 Correct 1141 ms 78424 KB Output is correct
8 Correct 1131 ms 78672 KB Output is correct
9 Correct 1272 ms 79204 KB Output is correct
10 Correct 330 ms 76880 KB Output is correct
11 Correct 1184 ms 78672 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 62300 KB Output is correct
2 Correct 6617 ms 364692 KB Output is correct
3 Execution timed out 8050 ms 484112 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62296 KB Output is correct
2 Correct 832 ms 78144 KB Output is correct
3 Correct 1151 ms 78640 KB Output is correct
4 Correct 927 ms 78764 KB Output is correct
5 Correct 1282 ms 79208 KB Output is correct
6 Correct 320 ms 76936 KB Output is correct
7 Correct 1141 ms 78424 KB Output is correct
8 Correct 1131 ms 78672 KB Output is correct
9 Correct 1272 ms 79204 KB Output is correct
10 Correct 330 ms 76880 KB Output is correct
11 Correct 1184 ms 78672 KB Output is correct
12 Correct 19 ms 62300 KB Output is correct
13 Correct 6617 ms 364692 KB Output is correct
14 Execution timed out 8050 ms 484112 KB Time limit exceeded
15 Halted 0 ms 0 KB -