oj.uz

Submission #961447

# Submission time Handle Problem Language Result Execution time Memory
961447 2024-04-12T06:19:59 Z kilkuwu Swapping Cities (APIO20_swap) C++17
53 / 100
 2000 ms 44260 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 (par[pu.first].second <= 1e9) {
    ckmin(par[num_nodes].second, w);
  }

  if (par[pv.first].second <= 1e9) {
    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);
  }

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

  std::cerr << u << " " << v << " " << w << " " << par[num_nodes].second << std::endl;
  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; 
}

/*

8 7
2 0 9
2 1 3
1 3 1
0 5 6
5 4 5
1 6 3
3 7 4
1 
0 4 


*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 7 ms 18944 KB Output is correct
5 Correct 11 ms 19036 KB Output is correct
6 Correct 11 ms 19032 KB Output is correct
7 Correct 12 ms 19036 KB Output is correct
8 Correct 13 ms 19036 KB Output is correct
9 Correct 790 ms 34264 KB Output is correct
10 Correct 960 ms 38356 KB Output is correct
11 Correct 912 ms 37380 KB Output is correct
12 Correct 954 ms 38736 KB Output is correct
13 Correct 964 ms 40204 KB Output is correct
14 Correct 768 ms 33848 KB Output is correct
15 Correct 1043 ms 42036 KB Output is correct
16 Correct 1040 ms 40480 KB Output is correct
17 Correct 1167 ms 44196 KB Output is correct
18 Correct 1112 ms 42948 KB Output is correct
19 Correct 262 ms 29072 KB Output is correct
20 Correct 1066 ms 42752 KB Output is correct
21 Correct 1099 ms 41688 KB Output is correct
22 Correct 1171 ms 43640 KB Output is correct
23 Correct 1102 ms 44016 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 972 ms 39808 KB Output is correct
4 Correct 1101 ms 40808 KB Output is correct
5 Correct 980 ms 41140 KB Output is correct
6 Correct 1040 ms 40240 KB Output is correct
7 Correct 984 ms 40144 KB Output is correct
8 Correct 986 ms 40508 KB Output is correct
9 Correct 1101 ms 40204 KB Output is correct
10 Correct 974 ms 39632 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 7 ms 18944 KB Output is correct
5 Correct 11 ms 19036 KB Output is correct
6 Correct 11 ms 19032 KB Output is correct
7 Correct 12 ms 19036 KB Output is correct
8 Correct 13 ms 19036 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 12 ms 19036 KB Output is correct
11 Correct 17 ms 18992 KB Output is correct
12 Correct 17 ms 19032 KB Output is correct
13 Correct 10 ms 19032 KB Output is correct
14 Correct 10 ms 19036 KB Output is correct
15 Correct 12 ms 19036 KB Output is correct
16 Correct 12 ms 19036 KB Output is correct
17 Correct 12 ms 19036 KB Output is correct
18 Correct 12 ms 18968 KB Output is correct
19 Correct 12 ms 19036 KB Output is correct
20 Correct 12 ms 18980 KB Output is correct
21 Correct 12 ms 14940 KB Output is correct
22 Correct 19 ms 19072 KB Output is correct
23 Correct 13 ms 19036 KB Output is correct
24 Correct 25 ms 19036 KB Output is correct
25 Correct 20 ms 19020 KB Output is correct
26 Correct 21 ms 19068 KB Output is correct
27 Correct 12 ms 18984 KB Output is correct
28 Correct 22 ms 18940 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 7 ms 18944 KB Output is correct
6 Correct 11 ms 19036 KB Output is correct
7 Correct 11 ms 19032 KB Output is correct
8 Correct 12 ms 19036 KB Output is correct
9 Correct 13 ms 19036 KB Output is correct
10 Correct 790 ms 34264 KB Output is correct
11 Correct 960 ms 38356 KB Output is correct
12 Correct 912 ms 37380 KB Output is correct
13 Correct 954 ms 38736 KB Output is correct
14 Correct 964 ms 40204 KB Output is correct
15 Correct 12 ms 19036 KB Output is correct
16 Correct 17 ms 18992 KB Output is correct
17 Correct 17 ms 19032 KB Output is correct
18 Correct 10 ms 19032 KB Output is correct
19 Correct 10 ms 19036 KB Output is correct
20 Correct 12 ms 19036 KB Output is correct
21 Correct 12 ms 19036 KB Output is correct
22 Correct 12 ms 19036 KB Output is correct
23 Correct 12 ms 18968 KB Output is correct
24 Correct 12 ms 19036 KB Output is correct
25 Correct 12 ms 18980 KB Output is correct
26 Correct 12 ms 14940 KB Output is correct
27 Correct 19 ms 19072 KB Output is correct
28 Correct 13 ms 19036 KB Output is correct
29 Correct 25 ms 19036 KB Output is correct
30 Correct 20 ms 19020 KB Output is correct
31 Correct 21 ms 19068 KB Output is correct
32 Correct 12 ms 18984 KB Output is correct
33 Correct 22 ms 18940 KB Output is correct
34 Correct 133 ms 22864 KB Output is correct
35 Correct 1004 ms 37888 KB Output is correct
36 Correct 942 ms 35556 KB Output is correct
37 Correct 971 ms 34164 KB Output is correct
38 Correct 969 ms 33560 KB Output is correct
39 Correct 1010 ms 33168 KB Output is correct
40 Correct 868 ms 32332 KB Output is correct
41 Correct 960 ms 36692 KB Output is correct
42 Correct 959 ms 37172 KB Output is correct
43 Correct 955 ms 37724 KB Output is correct
44 Correct 958 ms 34784 KB Output is correct
45 Correct 1490 ms 36720 KB Output is correct
46 Correct 968 ms 34868 KB Output is correct
47 Correct 970 ms 33380 KB Output is correct
48 Correct 1069 ms 34132 KB Output is correct
49 Correct 1508 ms 32032 KB Output is correct
50 Correct 1151 ms 30208 KB Output is correct
51 Correct 1227 ms 34524 KB Output is correct
52 Correct 1667 ms 39944 KB Output is correct
53 Correct 1819 ms 41188 KB Output is correct
54 Execution timed out 2009 ms 44260 KB Time limit exceeded
55 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18776 KB Output is correct
2 Correct 3 ms 18780 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 7 ms 18944 KB Output is correct
5 Correct 11 ms 19036 KB Output is correct
6 Correct 11 ms 19032 KB Output is correct
7 Correct 12 ms 19036 KB Output is correct
8 Correct 13 ms 19036 KB Output is correct
9 Correct 790 ms 34264 KB Output is correct
10 Correct 960 ms 38356 KB Output is correct
11 Correct 912 ms 37380 KB Output is correct
12 Correct 954 ms 38736 KB Output is correct
13 Correct 964 ms 40204 KB Output is correct
14 Correct 768 ms 33848 KB Output is correct
15 Correct 1043 ms 42036 KB Output is correct
16 Correct 1040 ms 40480 KB Output is correct
17 Correct 1167 ms 44196 KB Output is correct
18 Correct 1112 ms 42948 KB Output is correct
19 Correct 972 ms 39808 KB Output is correct
20 Correct 1101 ms 40808 KB Output is correct
21 Correct 980 ms 41140 KB Output is correct
22 Correct 1040 ms 40240 KB Output is correct
23 Correct 984 ms 40144 KB Output is correct
24 Correct 986 ms 40508 KB Output is correct
25 Correct 1101 ms 40204 KB Output is correct
26 Correct 974 ms 39632 KB Output is correct
27 Correct 12 ms 19036 KB Output is correct
28 Correct 17 ms 18992 KB Output is correct
29 Correct 17 ms 19032 KB Output is correct
30 Correct 10 ms 19032 KB Output is correct
31 Correct 10 ms 19036 KB Output is correct
32 Correct 12 ms 19036 KB Output is correct
33 Correct 12 ms 19036 KB Output is correct
34 Correct 12 ms 19036 KB Output is correct
35 Correct 12 ms 18968 KB Output is correct
36 Correct 133 ms 22864 KB Output is correct
37 Correct 1004 ms 37888 KB Output is correct
38 Correct 942 ms 35556 KB Output is correct
39 Correct 971 ms 34164 KB Output is correct
40 Correct 969 ms 33560 KB Output is correct
41 Correct 1010 ms 33168 KB Output is correct
42 Correct 868 ms 32332 KB Output is correct
43 Correct 960 ms 36692 KB Output is correct
44 Correct 959 ms 37172 KB Output is correct
45 Correct 955 ms 37724 KB Output is correct
46 Correct 958 ms 34784 KB Output is correct
47 Correct 132 ms 23136 KB Output is correct
48 Correct 1173 ms 41180 KB Output is correct
49 Correct 1196 ms 39848 KB Output is correct
50 Correct 1214 ms 38920 KB Output is correct
51 Correct 1199 ms 38496 KB Output is correct
52 Correct 1049 ms 37496 KB Output is correct
53 Correct 775 ms 35704 KB Output is correct
54 Correct 1285 ms 37252 KB Output is correct
55 Correct 1213 ms 39692 KB Output is correct
56 Correct 1254 ms 41352 KB Output is correct
57 Correct 1163 ms 35476 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18780 KB Output is correct
2 Correct 3 ms 18776 KB Output is correct
3 Correct 3 ms 18780 KB Output is correct
4 Correct 3 ms 18780 KB Output is correct
5 Correct 7 ms 18944 KB Output is correct
6 Correct 11 ms 19036 KB Output is correct
7 Correct 11 ms 19032 KB Output is correct
8 Correct 12 ms 19036 KB Output is correct
9 Correct 13 ms 19036 KB Output is correct
10 Correct 790 ms 34264 KB Output is correct
11 Correct 960 ms 38356 KB Output is correct
12 Correct 912 ms 37380 KB Output is correct
13 Correct 954 ms 38736 KB Output is correct
14 Correct 964 ms 40204 KB Output is correct
15 Correct 768 ms 33848 KB Output is correct
16 Correct 1043 ms 42036 KB Output is correct
17 Correct 1040 ms 40480 KB Output is correct
18 Correct 1167 ms 44196 KB Output is correct
19 Correct 1112 ms 42948 KB Output is correct
20 Correct 972 ms 39808 KB Output is correct
21 Correct 1101 ms 40808 KB Output is correct
22 Correct 980 ms 41140 KB Output is correct
23 Correct 1040 ms 40240 KB Output is correct
24 Correct 984 ms 40144 KB Output is correct
25 Correct 986 ms 40508 KB Output is correct
26 Correct 1101 ms 40204 KB Output is correct
27 Correct 974 ms 39632 KB Output is correct
28 Correct 12 ms 19036 KB Output is correct
29 Correct 17 ms 18992 KB Output is correct
30 Correct 17 ms 19032 KB Output is correct
31 Correct 10 ms 19032 KB Output is correct
32 Correct 10 ms 19036 KB Output is correct
33 Correct 12 ms 19036 KB Output is correct
34 Correct 12 ms 19036 KB Output is correct
35 Correct 12 ms 19036 KB Output is correct
36 Correct 12 ms 18968 KB Output is correct
37 Correct 133 ms 22864 KB Output is correct
38 Correct 1004 ms 37888 KB Output is correct
39 Correct 942 ms 35556 KB Output is correct
40 Correct 971 ms 34164 KB Output is correct
41 Correct 969 ms 33560 KB Output is correct
42 Correct 1010 ms 33168 KB Output is correct
43 Correct 868 ms 32332 KB Output is correct
44 Correct 960 ms 36692 KB Output is correct
45 Correct 959 ms 37172 KB Output is correct
46 Correct 955 ms 37724 KB Output is correct
47 Correct 958 ms 34784 KB Output is correct
48 Correct 132 ms 23136 KB Output is correct
49 Correct 1173 ms 41180 KB Output is correct
50 Correct 1196 ms 39848 KB Output is correct
51 Correct 1214 ms 38920 KB Output is correct
52 Correct 1199 ms 38496 KB Output is correct
53 Correct 1049 ms 37496 KB Output is correct
54 Correct 775 ms 35704 KB Output is correct
55 Correct 1285 ms 37252 KB Output is correct
56 Correct 1213 ms 39692 KB Output is correct
57 Correct 1254 ms 41352 KB Output is correct
58 Correct 1163 ms 35476 KB Output is correct
59 Correct 262 ms 29072 KB Output is correct
60 Correct 1066 ms 42752 KB Output is correct
61 Correct 1099 ms 41688 KB Output is correct
62 Correct 1171 ms 43640 KB Output is correct
63 Correct 1102 ms 44016 KB Output is correct
64 Correct 12 ms 19036 KB Output is correct
65 Correct 12 ms 18980 KB Output is correct
66 Correct 12 ms 14940 KB Output is correct
67 Correct 19 ms 19072 KB Output is correct
68 Correct 13 ms 19036 KB Output is correct
69 Correct 25 ms 19036 KB Output is correct
70 Correct 20 ms 19020 KB Output is correct
71 Correct 21 ms 19068 KB Output is correct
72 Correct 12 ms 18984 KB Output is correct
73 Correct 22 ms 18940 KB Output is correct
74 Correct 1490 ms 36720 KB Output is correct
75 Correct 968 ms 34868 KB Output is correct
76 Correct 970 ms 33380 KB Output is correct
77 Correct 1069 ms 34132 KB Output is correct
78 Correct 1508 ms 32032 KB Output is correct
79 Correct 1151 ms 30208 KB Output is correct
80 Correct 1227 ms 34524 KB Output is correct
81 Correct 1667 ms 39944 KB Output is correct
82 Correct 1819 ms 41188 KB Output is correct
83 Execution timed out 2009 ms 44260 KB Time limit exceeded
84 Halted 0 ms 0 KB -