oj.uz

Submission #961439

# Submission time Handle Problem Language Result Execution time Memory
961439 2024-04-12T06:04:17 Z kilkuwu Swapping Cities (APIO20_swap) C++17
13 / 100
 275 ms 40872 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);

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

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

  if (adj[u].size() > 2 || adj[v].size() > 2) {
    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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18888 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 18912 KB Output is correct
9 Correct 54 ms 31608 KB Output is correct
10 Correct 57 ms 34976 KB Output is correct
11 Correct 62 ms 34436 KB Output is correct
12 Correct 71 ms 35416 KB Output is correct
13 Correct 55 ms 36944 KB Output is correct
14 Correct 75 ms 31388 KB Output is correct
15 Correct 209 ms 38880 KB Output is correct
16 Correct 207 ms 37392 KB Output is correct
17 Correct 192 ms 40872 KB Output is correct
18 Correct 256 ms 39636 KB Output is correct
19 Correct 65 ms 28564 KB Output is correct
20 Correct 218 ms 39468 KB Output is correct
21 Correct 270 ms 38760 KB Output is correct
22 Correct 205 ms 40512 KB Output is correct
23 Correct 275 ms 40736 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18888 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 117 ms 37104 KB Output is correct
4 Correct 156 ms 38188 KB Output is correct
5 Correct 128 ms 38388 KB Output is correct
6 Correct 113 ms 38188 KB Output is correct
7 Correct 125 ms 37580 KB Output is correct
8 Correct 136 ms 38084 KB Output is correct
9 Correct 118 ms 37444 KB Output is correct
10 Correct 113 ms 37156 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18888 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 18912 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 4 ms 19036 KB Output is correct
11 Incorrect 3 ms 19068 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 18888 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 4 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 19032 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 18912 KB Output is correct
10 Correct 54 ms 31608 KB Output is correct
11 Correct 57 ms 34976 KB Output is correct
12 Correct 62 ms 34436 KB Output is correct
13 Correct 71 ms 35416 KB Output is correct
14 Correct 55 ms 36944 KB Output is correct
15 Correct 4 ms 19036 KB Output is correct
16 Incorrect 3 ms 19068 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 18888 KB Output is correct
2 Correct 4 ms 18780 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 3 ms 19036 KB Output is correct
6 Correct 3 ms 19032 KB Output is correct
7 Correct 3 ms 19036 KB Output is correct
8 Correct 3 ms 18912 KB Output is correct
9 Correct 54 ms 31608 KB Output is correct
10 Correct 57 ms 34976 KB Output is correct
11 Correct 62 ms 34436 KB Output is correct
12 Correct 71 ms 35416 KB Output is correct
13 Correct 55 ms 36944 KB Output is correct
14 Correct 75 ms 31388 KB Output is correct
15 Correct 209 ms 38880 KB Output is correct
16 Correct 207 ms 37392 KB Output is correct
17 Correct 192 ms 40872 KB Output is correct
18 Correct 256 ms 39636 KB Output is correct
19 Correct 117 ms 37104 KB Output is correct
20 Correct 156 ms 38188 KB Output is correct
21 Correct 128 ms 38388 KB Output is correct
22 Correct 113 ms 38188 KB Output is correct
23 Correct 125 ms 37580 KB Output is correct
24 Correct 136 ms 38084 KB Output is correct
25 Correct 118 ms 37444 KB Output is correct
26 Correct 113 ms 37156 KB Output is correct
27 Correct 4 ms 19036 KB Output is correct
28 Incorrect 3 ms 19068 KB Output isn't correct
29 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 18888 KB Output is correct
3 Correct 4 ms 18780 KB Output is correct
4 Correct 4 ms 18780 KB Output is correct
5 Correct 3 ms 18780 KB Output is correct
6 Correct 3 ms 19036 KB Output is correct
7 Correct 3 ms 19032 KB Output is correct
8 Correct 3 ms 19036 KB Output is correct
9 Correct 3 ms 18912 KB Output is correct
10 Correct 54 ms 31608 KB Output is correct
11 Correct 57 ms 34976 KB Output is correct
12 Correct 62 ms 34436 KB Output is correct
13 Correct 71 ms 35416 KB Output is correct
14 Correct 55 ms 36944 KB Output is correct
15 Correct 75 ms 31388 KB Output is correct
16 Correct 209 ms 38880 KB Output is correct
17 Correct 207 ms 37392 KB Output is correct
18 Correct 192 ms 40872 KB Output is correct
19 Correct 256 ms 39636 KB Output is correct
20 Correct 117 ms 37104 KB Output is correct
21 Correct 156 ms 38188 KB Output is correct
22 Correct 128 ms 38388 KB Output is correct
23 Correct 113 ms 38188 KB Output is correct
24 Correct 125 ms 37580 KB Output is correct
25 Correct 136 ms 38084 KB Output is correct
26 Correct 118 ms 37444 KB Output is correct
27 Correct 113 ms 37156 KB Output is correct
28 Correct 4 ms 19036 KB Output is correct
29 Incorrect 3 ms 19068 KB Output isn't correct
30 Halted 0 ms 0 KB -