oj.uz

Submission #961434

# Submission time Handle Problem Language Result Execution time Memory
961434 2024-04-12T05:44:09 Z kilkuwu Swapping Cities (APIO20_swap) C++17
6 / 100
 263 ms 40900 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];

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) {
  auto pu = find(u), pv = find(v);

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

  if (pu.first == pv.first) {
    ckmin(par[num_nodes].second, w);
  } else {
    adj[u].emplace_back(w, v);
    adj[v].emplace_back(w, u);
  }

  par[pu.first].first = par[pv.first].first = num_nodes;

  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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 3 ms 18992 KB Output is correct
5 Correct 3 ms 18912 KB Output is correct
6 Correct 4 ms 18892 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 51 ms 31568 KB Output is correct
10 Correct 56 ms 34900 KB Output is correct
11 Correct 60 ms 34512 KB Output is correct
12 Correct 75 ms 35408 KB Output is correct
13 Correct 57 ms 36784 KB Output is correct
14 Correct 59 ms 31320 KB Output is correct
15 Correct 200 ms 38744 KB Output is correct
16 Correct 249 ms 37364 KB Output is correct
17 Correct 178 ms 40900 KB Output is correct
18 Correct 226 ms 39736 KB Output is correct
19 Correct 65 ms 28496 KB Output is correct
20 Correct 210 ms 39300 KB Output is correct
21 Correct 263 ms 38720 KB Output is correct
22 Correct 205 ms 40292 KB Output is correct
23 Correct 190 ms 40660 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 114 ms 36980 KB Output is correct
4 Correct 118 ms 38184 KB Output is correct
5 Correct 126 ms 38192 KB Output is correct
6 Correct 127 ms 38192 KB Output is correct
7 Incorrect 116 ms 37448 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 3 ms 18992 KB Output is correct
5 Correct 3 ms 18912 KB Output is correct
6 Correct 4 ms 18892 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 3 ms 19036 KB Output is correct
11 Incorrect 3 ms 18968 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 19032 KB Output is correct
5 Correct 3 ms 18992 KB Output is correct
6 Correct 3 ms 18912 KB Output is correct
7 Correct 4 ms 18892 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 51 ms 31568 KB Output is correct
11 Correct 56 ms 34900 KB Output is correct
12 Correct 60 ms 34512 KB Output is correct
13 Correct 75 ms 35408 KB Output is correct
14 Correct 57 ms 36784 KB Output is correct
15 Correct 3 ms 19036 KB Output is correct
16 Incorrect 3 ms 18968 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 19032 KB Output is correct
4 Correct 3 ms 18992 KB Output is correct
5 Correct 3 ms 18912 KB Output is correct
6 Correct 4 ms 18892 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 51 ms 31568 KB Output is correct
10 Correct 56 ms 34900 KB Output is correct
11 Correct 60 ms 34512 KB Output is correct
12 Correct 75 ms 35408 KB Output is correct
13 Correct 57 ms 36784 KB Output is correct
14 Correct 59 ms 31320 KB Output is correct
15 Correct 200 ms 38744 KB Output is correct
16 Correct 249 ms 37364 KB Output is correct
17 Correct 178 ms 40900 KB Output is correct
18 Correct 226 ms 39736 KB Output is correct
19 Correct 114 ms 36980 KB Output is correct
20 Correct 118 ms 38184 KB Output is correct
21 Correct 126 ms 38192 KB Output is correct
22 Correct 127 ms 38192 KB Output is correct
23 Incorrect 116 ms 37448 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 19032 KB Output is correct
5 Correct 3 ms 18992 KB Output is correct
6 Correct 3 ms 18912 KB Output is correct
7 Correct 4 ms 18892 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Correct 51 ms 31568 KB Output is correct
11 Correct 56 ms 34900 KB Output is correct
12 Correct 60 ms 34512 KB Output is correct
13 Correct 75 ms 35408 KB Output is correct
14 Correct 57 ms 36784 KB Output is correct
15 Correct 59 ms 31320 KB Output is correct
16 Correct 200 ms 38744 KB Output is correct
17 Correct 249 ms 37364 KB Output is correct
18 Correct 178 ms 40900 KB Output is correct
19 Correct 226 ms 39736 KB Output is correct
20 Correct 114 ms 36980 KB Output is correct
21 Correct 118 ms 38184 KB Output is correct
22 Correct 126 ms 38192 KB Output is correct
23 Correct 127 ms 38192 KB Output is correct
24 Incorrect 116 ms 37448 KB Output isn't correct
25 Halted 0 ms 0 KB -