oj.uz

Submission #961419

# Submission time Handle Problem Language Result Execution time Memory
961419 2024-04-12T04:54:17 Z kilkuwu Swapping Cities (APIO20_swap) C++17
0 / 100
 627 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 = find(X).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 4 ms 18780 KB Output is correct
2 Correct 5 ms 18920 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18776 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 3 ms 19032 KB Output is correct
9 Correct 43 ms 31568 KB Output is correct
10 Correct 53 ms 34900 KB Output is correct
11 Correct 57 ms 34388 KB Output is correct
12 Correct 59 ms 35280 KB Output is correct
13 Correct 55 ms 36688 KB Output is correct
14 Correct 54 ms 31480 KB Output is correct
15 Correct 172 ms 38868 KB Output is correct
16 Correct 191 ms 37392 KB Output is correct
17 Correct 166 ms 40744 KB Output is correct
18 Correct 174 ms 39868 KB Output is correct
19 Runtime error 627 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 4 ms 18780 KB Output is correct
2 Correct 5 ms 18920 KB Output is correct
3 Incorrect 114 ms 34476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 18780 KB Output is correct
2 Correct 5 ms 18920 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18776 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 3 ms 19032 KB Output is correct
9 Runtime error 285 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 285 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 4 ms 18780 KB Output is correct
2 Correct 5 ms 18920 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18776 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 3 ms 19032 KB Output is correct
9 Correct 43 ms 31568 KB Output is correct
10 Correct 53 ms 34900 KB Output is correct
11 Correct 57 ms 34388 KB Output is correct
12 Correct 59 ms 35280 KB Output is correct
13 Correct 55 ms 36688 KB Output is correct
14 Correct 54 ms 31480 KB Output is correct
15 Correct 172 ms 38868 KB Output is correct
16 Correct 191 ms 37392 KB Output is correct
17 Correct 166 ms 40744 KB Output is correct
18 Correct 174 ms 39868 KB Output is correct
19 Incorrect 114 ms 34476 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 285 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -