oj.uz

Submission #869495

# Submission time Handle Problem Language Result Execution time Memory
869495 2023-11-04T13:38:06 Z tch1cherin Swapping Cities (APIO20_swap) C++17
100 / 100
 519 ms 69056 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

struct merging_dsu {
  vector<int> parent, cnt_v, cnt_e, deg, max_deg, T;
  vector<vector<int>> comp;

  merging_dsu(int size) : parent(size), cnt_v(size, 1), cnt_e(size), deg(size), max_deg(size), T(size, INT_MAX), comp(size) {
    iota(parent.begin(), parent.end(), 0);
    for (int i = 0; i < size; i++) {
      comp[i] = {i};
    }
  }

  int get(int u) {
    return parent[u] == u ? u : (parent[u] = get(parent[u]));
  }

  void unite(int u, int v, int w) {
    int new_val = max(++deg[u], ++deg[v]);
    u = get(u), v = get(v);
    if (u != v) {
      if (cnt_v[u] < cnt_v[v]) {
        swap(u, v);
      }
      parent[v] = u;
      cnt_v[u] += cnt_v[v];
      cnt_e[u] += cnt_e[v];
      max_deg[u] = max(max_deg[u], max_deg[v]);
      for (int x : comp[v]) {
        comp[u].push_back(x);
      }
    }
    max_deg[u] = max(max_deg[u], new_val);
    cnt_e[u]++;
    if (cnt_e[u] >= cnt_v[u] || max_deg[u] > 2) {
      for (int x : comp[u]) {
        T[x] = w;
      }
      comp[u] = vector<int>();
    }
  }
};

struct dsu {
  vector<int> parent, rank;

  dsu(int size) : parent(size), rank(size, 1) {
    iota(parent.begin(), parent.end(), 0);
  }

  int get(int u) {
    return parent[u] == u ? u : (parent[u] = get(parent[u]));
  }

  bool unite(int u, int v) {
    u = get(u), v = get(v);
    if (u != v) {
      if (rank[u] < rank[v]) {
        swap(u, v);
      }
      parent[v] = u;
      rank[u] += rank[v];
      return true;
    }
    return false;
  }
};

const int MAX_L = 20;

struct binary_lifting {
  vector<vector<array<int, 2>>> graph;
  vector<vector<int>> up, dp;
  vector<int> depth;

  binary_lifting() {}

  binary_lifting(vector<vector<array<int, 2>>> _graph) : graph(_graph) {
    int N = (int)graph.size();
    depth = vector<int>(N);
    up = vector<vector<int>>(N, vector<int>(MAX_L));
    dp = vector<vector<int>>(N, vector<int>(MAX_L, INT_MIN));
    DFS(0, 0);
  }

  void DFS(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < MAX_L; i++) {
      up[u][i] = up[up[u][i - 1]][i - 1];
      dp[u][i] = max(dp[u][i - 1], dp[up[u][i - 1]][i - 1]);
    }
    for (auto [v, w] : graph[u]) {
      if (v != p) {
        depth[v] = depth[u] + 1;
        dp[v][0] = w;
        DFS(v, u);
      }
    }
  }

  int query(int u, int v) {
    if (depth[u] < depth[v]) {
      swap(u, v);
    }
    int ans = INT_MIN;
    for (int i = MAX_L - 1; i >= 0; i--) {
      if (depth[u] - (1 << i) >= depth[v]) {
        ans = max(ans, dp[u][i]);
        u = up[u][i];
      }
    }
    if (u == v) {
      return ans;
    }
    for (int i = MAX_L - 1; i >= 0; i--) {
      if (up[u][i] != up[v][i]) {
        ans = max({ans, dp[u][i], dp[v][i]});
        u = up[u][i];
        v = up[v][i];
      }
    }
    return max({ans, dp[u][0], dp[v][0]});
  }
};

binary_lifting BL;
vector<int> T;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  vector<vector<array<int, 2>>> graph(N);
  vector<array<int, 3>> edges;
  for (int i = 0; i < M; i++) {
    edges.push_back({W[i], U[i], V[i]});
  }
  sort(edges.begin(), edges.end());
  dsu sets(N);
  merging_dsu D(N);
  for (auto [W, U, V] : edges) {
    D.unite(U, V, W);
    if (sets.unite(U, V)) {
      graph[U].push_back({V, W});
      graph[V].push_back({U, W});
    }
  }
  T = D.T;
  BL = binary_lifting(graph);
}

int getMinimumFuelCapacity(int X, int Y) {
  int value = max(T[X], BL.query(X, Y));
  return value == INT_MAX ? -1 : value;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 137 ms 47332 KB Output is correct
10 Correct 190 ms 58308 KB Output is correct
11 Correct 203 ms 56968 KB Output is correct
12 Correct 220 ms 60612 KB Output is correct
13 Correct 211 ms 59076 KB Output is correct
14 Correct 190 ms 47588 KB Output is correct
15 Correct 500 ms 62368 KB Output is correct
16 Correct 519 ms 60140 KB Output is correct
17 Correct 485 ms 65224 KB Output is correct
18 Correct 421 ms 62536 KB Output is correct
19 Correct 96 ms 13076 KB Output is correct
20 Correct 417 ms 61896 KB Output is correct
21 Correct 426 ms 59180 KB Output is correct
22 Correct 478 ms 63880 KB Output is correct
23 Correct 477 ms 61892 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 227 ms 57796 KB Output is correct
4 Correct 275 ms 60760 KB Output is correct
5 Correct 219 ms 58848 KB Output is correct
6 Correct 234 ms 60360 KB Output is correct
7 Correct 217 ms 59844 KB Output is correct
8 Correct 211 ms 57260 KB Output is correct
9 Correct 215 ms 59352 KB Output is correct
10 Correct 255 ms 57164 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 856 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 860 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 1 ms 860 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 2 ms 1108 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 1 ms 860 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 1 ms 860 KB Output is correct
27 Correct 1 ms 860 KB Output is correct
28 Correct 2 ms 992 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 137 ms 47332 KB Output is correct
11 Correct 190 ms 58308 KB Output is correct
12 Correct 203 ms 56968 KB Output is correct
13 Correct 220 ms 60612 KB Output is correct
14 Correct 211 ms 59076 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 860 KB Output is correct
17 Correct 1 ms 860 KB Output is correct
18 Correct 1 ms 856 KB Output is correct
19 Correct 1 ms 860 KB Output is correct
20 Correct 1 ms 860 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 1 ms 860 KB Output is correct
23 Correct 1 ms 860 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 860 KB Output is correct
26 Correct 2 ms 1108 KB Output is correct
27 Correct 1 ms 604 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 2 ms 992 KB Output is correct
34 Correct 16 ms 7964 KB Output is correct
35 Correct 197 ms 59412 KB Output is correct
36 Correct 202 ms 58128 KB Output is correct
37 Correct 190 ms 56516 KB Output is correct
38 Correct 165 ms 54984 KB Output is correct
39 Correct 155 ms 54700 KB Output is correct
40 Correct 140 ms 49568 KB Output is correct
41 Correct 186 ms 59124 KB Output is correct
42 Correct 189 ms 59356 KB Output is correct
43 Correct 199 ms 57544 KB Output is correct
44 Correct 142 ms 55844 KB Output is correct
45 Correct 147 ms 47812 KB Output is correct
46 Correct 218 ms 57908 KB Output is correct
47 Correct 157 ms 55620 KB Output is correct
48 Correct 137 ms 54840 KB Output is correct
49 Correct 56 ms 9936 KB Output is correct
50 Correct 43 ms 10696 KB Output is correct
51 Correct 117 ms 39300 KB Output is correct
52 Correct 220 ms 61892 KB Output is correct
53 Correct 170 ms 59688 KB Output is correct
54 Correct 232 ms 64184 KB Output is correct
55 Correct 178 ms 58068 KB Output is correct
56 Correct 185 ms 60576 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 137 ms 47332 KB Output is correct
10 Correct 190 ms 58308 KB Output is correct
11 Correct 203 ms 56968 KB Output is correct
12 Correct 220 ms 60612 KB Output is correct
13 Correct 211 ms 59076 KB Output is correct
14 Correct 190 ms 47588 KB Output is correct
15 Correct 500 ms 62368 KB Output is correct
16 Correct 519 ms 60140 KB Output is correct
17 Correct 485 ms 65224 KB Output is correct
18 Correct 421 ms 62536 KB Output is correct
19 Correct 227 ms 57796 KB Output is correct
20 Correct 275 ms 60760 KB Output is correct
21 Correct 219 ms 58848 KB Output is correct
22 Correct 234 ms 60360 KB Output is correct
23 Correct 217 ms 59844 KB Output is correct
24 Correct 211 ms 57260 KB Output is correct
25 Correct 215 ms 59352 KB Output is correct
26 Correct 255 ms 57164 KB Output is correct
27 Correct 1 ms 1116 KB Output is correct
28 Correct 1 ms 860 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 1 ms 856 KB Output is correct
31 Correct 1 ms 860 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 860 KB Output is correct
35 Correct 1 ms 860 KB Output is correct
36 Correct 16 ms 7964 KB Output is correct
37 Correct 197 ms 59412 KB Output is correct
38 Correct 202 ms 58128 KB Output is correct
39 Correct 190 ms 56516 KB Output is correct
40 Correct 165 ms 54984 KB Output is correct
41 Correct 155 ms 54700 KB Output is correct
42 Correct 140 ms 49568 KB Output is correct
43 Correct 186 ms 59124 KB Output is correct
44 Correct 189 ms 59356 KB Output is correct
45 Correct 199 ms 57544 KB Output is correct
46 Correct 142 ms 55844 KB Output is correct
47 Correct 21 ms 7448 KB Output is correct
48 Correct 461 ms 62664 KB Output is correct
49 Correct 426 ms 61316 KB Output is correct
50 Correct 393 ms 60504 KB Output is correct
51 Correct 398 ms 59448 KB Output is correct
52 Correct 317 ms 55648 KB Output is correct
53 Correct 205 ms 40904 KB Output is correct
54 Correct 464 ms 62504 KB Output is correct
55 Correct 467 ms 63176 KB Output is correct
56 Correct 384 ms 61912 KB Output is correct
57 Correct 289 ms 59588 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 137 ms 47332 KB Output is correct
11 Correct 190 ms 58308 KB Output is correct
12 Correct 203 ms 56968 KB Output is correct
13 Correct 220 ms 60612 KB Output is correct
14 Correct 211 ms 59076 KB Output is correct
15 Correct 190 ms 47588 KB Output is correct
16 Correct 500 ms 62368 KB Output is correct
17 Correct 519 ms 60140 KB Output is correct
18 Correct 485 ms 65224 KB Output is correct
19 Correct 421 ms 62536 KB Output is correct
20 Correct 227 ms 57796 KB Output is correct
21 Correct 275 ms 60760 KB Output is correct
22 Correct 219 ms 58848 KB Output is correct
23 Correct 234 ms 60360 KB Output is correct
24 Correct 217 ms 59844 KB Output is correct
25 Correct 211 ms 57260 KB Output is correct
26 Correct 215 ms 59352 KB Output is correct
27 Correct 255 ms 57164 KB Output is correct
28 Correct 1 ms 1116 KB Output is correct
29 Correct 1 ms 860 KB Output is correct
30 Correct 1 ms 860 KB Output is correct
31 Correct 1 ms 856 KB Output is correct
32 Correct 1 ms 860 KB Output is correct
33 Correct 1 ms 860 KB Output is correct
34 Correct 1 ms 860 KB Output is correct
35 Correct 1 ms 860 KB Output is correct
36 Correct 1 ms 860 KB Output is correct
37 Correct 16 ms 7964 KB Output is correct
38 Correct 197 ms 59412 KB Output is correct
39 Correct 202 ms 58128 KB Output is correct
40 Correct 190 ms 56516 KB Output is correct
41 Correct 165 ms 54984 KB Output is correct
42 Correct 155 ms 54700 KB Output is correct
43 Correct 140 ms 49568 KB Output is correct
44 Correct 186 ms 59124 KB Output is correct
45 Correct 189 ms 59356 KB Output is correct
46 Correct 199 ms 57544 KB Output is correct
47 Correct 142 ms 55844 KB Output is correct
48 Correct 21 ms 7448 KB Output is correct
49 Correct 461 ms 62664 KB Output is correct
50 Correct 426 ms 61316 KB Output is correct
51 Correct 393 ms 60504 KB Output is correct
52 Correct 398 ms 59448 KB Output is correct
53 Correct 317 ms 55648 KB Output is correct
54 Correct 205 ms 40904 KB Output is correct
55 Correct 464 ms 62504 KB Output is correct
56 Correct 467 ms 63176 KB Output is correct
57 Correct 384 ms 61912 KB Output is correct
58 Correct 289 ms 59588 KB Output is correct
59 Correct 96 ms 13076 KB Output is correct
60 Correct 417 ms 61896 KB Output is correct
61 Correct 426 ms 59180 KB Output is correct
62 Correct 478 ms 63880 KB Output is correct
63 Correct 477 ms 61892 KB Output is correct
64 Correct 1 ms 604 KB Output is correct
65 Correct 1 ms 860 KB Output is correct
66 Correct 2 ms 1108 KB Output is correct
67 Correct 1 ms 604 KB Output is correct
68 Correct 1 ms 860 KB Output is correct
69 Correct 1 ms 860 KB Output is correct
70 Correct 1 ms 860 KB Output is correct
71 Correct 1 ms 860 KB Output is correct
72 Correct 1 ms 860 KB Output is correct
73 Correct 2 ms 992 KB Output is correct
74 Correct 147 ms 47812 KB Output is correct
75 Correct 218 ms 57908 KB Output is correct
76 Correct 157 ms 55620 KB Output is correct
77 Correct 137 ms 54840 KB Output is correct
78 Correct 56 ms 9936 KB Output is correct
79 Correct 43 ms 10696 KB Output is correct
80 Correct 117 ms 39300 KB Output is correct
81 Correct 220 ms 61892 KB Output is correct
82 Correct 170 ms 59688 KB Output is correct
83 Correct 232 ms 64184 KB Output is correct
84 Correct 178 ms 58068 KB Output is correct
85 Correct 185 ms 60576 KB Output is correct
86 Correct 67 ms 19524 KB Output is correct
87 Correct 434 ms 61116 KB Output is correct
88 Correct 393 ms 61128 KB Output is correct
89 Correct 282 ms 55664 KB Output is correct
90 Correct 117 ms 15044 KB Output is correct
91 Correct 132 ms 17600 KB Output is correct
92 Correct 204 ms 43204 KB Output is correct
93 Correct 437 ms 64644 KB Output is correct
94 Correct 308 ms 64196 KB Output is correct
95 Correct 519 ms 69056 KB Output is correct
96 Correct 481 ms 60876 KB Output is correct
97 Correct 290 ms 61888 KB Output is correct