oj.uz

Submission #961420

# Submission time Handle Problem Language Result Execution time Memory
961420 2024-04-12T04:59:21 Z kilkuwu Swapping Cities (APIO20_swap) C++17
0 / 100
 652 ms 524288 KB 
#include "swap.h"

#include <bits/stdc++.h>

template <typename T>
inline bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}

template <typename T>
inline bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}

constexpr int mxM = 200'000;
constexpr int mxN = 100'000;
constexpr int LOG = 20;
constexpr int inf = 1e9 + 7;

struct Edge {
  int u, v, w;

  bool operator<(const Edge& rhs) const {
    return w < rhs.w;
  }

  inline int other(int x) { return u ^ v ^ x; }
};

Edge edges[mxM];
std::vector<std::pair<int, int>> adj[mxN];

int up[LOG][mxN];
int vv[LOG][mxN];
int dep[mxN];

int num_nodes;

std::pair<int, int> par[mxN + mxM];
// we need to find first cycle and first three;

std::pair<int, int> find(int u) {
  if (par[u].first == -1) {
    return {u, par[u].second};
  }

  auto pu = find(par[u].first);
  pu.second = std::min(pu.second, par[u].second);

  return par[u] = pu;
}

void merge(int u, int v, int w) {
  adj[u].emplace_back(w, v);
  adj[v].emplace_back(w, u);

  auto pu = find(u), pv = find(v);

  if (adj[u].size() > 2 || adj[v].size() > 2) {
    ckmin(par[num_nodes].second, w);
  }

  if (pu == pv) {
    ckmin(par[num_nodes].second, w);
  }

  num_nodes++;
}

void dfs(int u) {
  for (auto [w, v] : adj[u]) {
    if (v == up[0][u]) continue;
    dep[v] = dep[u] + 1;
    up[0][v] = u;
    vv[0][v] = w;
    dfs(v);
  } 
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  
  for (int i = 0; i < N + M; i++) {
    par[i] = {-1, inf};
  }

  num_nodes = N;
  for (int i = 0; i < M; i++) {
    edges[i] = {U[i], V[i], W[i]};
  }

  std::sort(edges, edges + M);

  for (int i = 0; i < M; i++) {
    auto [u, v, w] = edges[i];
    merge(u, v, w);
  }

  dfs(0);

  for (int k = 0; k + 1 < LOG; k++) {
    for (int i = 0; i < N; i++) {
      up[k + 1][i] = up[k][up[k][i]];
      vv[k + 1][i] = std::max(vv[k][i], vv[k][up[k][i]]);
    }
  }
}

int max_path(int u, int v) {
  if (dep[u] > dep[v]) std::swap(u, v);
  int d = dep[v] - dep[u];
  int ans = 0;
  for (int k = 0; k < LOG; k++) {
    if (d >> k & 1) {
      ckmax(ans, vv[k][v]);
      v = up[k][v];
    }
  }

  if (u == v) return ans;

  for (int k = LOG - 1; k >= 0; k--) {
    if (up[k][u] != up[k][v]) {
      ckmax(ans, vv[k][u]);
      ckmax(ans, vv[k][v]);
      u = up[k][u];
      v = up[k][v];
    }
  }

  ckmax(ans, vv[0][u]);
  ckmax(ans, vv[0][v]);

  return ans;
}

int getMinimumFuelCapacity(int X, int Y) {
  int ans = std::min(find(X).second, find(Y).second);
  ans = std::max(ans, max_path(X, Y));
  return ans <= 1e9 ? ans : -1; 
}

#ifdef LOCAL

#endif

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18780 KB Output is correct
2 Correct 3 ms 18928 KB Output is correct
3 Correct 4 ms 18872 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 6 ms 19032 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 45 ms 29780 KB Output is correct
10 Correct 54 ms 32932 KB Output is correct
11 Correct 55 ms 32340 KB Output is correct
12 Correct 67 ms 33312 KB Output is correct
13 Correct 63 ms 34656 KB Output is correct
14 Correct 55 ms 29520 KB Output is correct
15 Correct 188 ms 34520 KB Output is correct
16 Correct 188 ms 33120 KB Output is correct
17 Correct 157 ms 36540 KB Output is correct
18 Correct 186 ms 35256 KB Output is correct
19 Runtime error 652 ms 524288 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18780 KB Output is correct
2 Correct 3 ms 18928 KB Output is correct
3 Incorrect 106 ms 30568 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18780 KB Output is correct
2 Correct 3 ms 18928 KB Output is correct
3 Correct 4 ms 18872 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 6 ms 19032 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Runtime error 290 ms 524288 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 290 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 18780 KB Output is correct
2 Correct 3 ms 18928 KB Output is correct
3 Correct 4 ms 18872 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 6 ms 19032 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 45 ms 29780 KB Output is correct
10 Correct 54 ms 32932 KB Output is correct
11 Correct 55 ms 32340 KB Output is correct
12 Correct 67 ms 33312 KB Output is correct
13 Correct 63 ms 34656 KB Output is correct
14 Correct 55 ms 29520 KB Output is correct
15 Correct 188 ms 34520 KB Output is correct
16 Correct 188 ms 33120 KB Output is correct
17 Correct 157 ms 36540 KB Output is correct
18 Correct 186 ms 35256 KB Output is correct
19 Incorrect 106 ms 30568 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 290 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -