oj.uz

Submission #701752

# Submission time Handle Problem Language Result Execution time Memory
701752 2023-02-22T04:00:03 Z dattranxxx Swapping Cities (APIO20_swap) C++11
100 / 100
 380 ms 62528 KB 
#include <bits/stdc++.h>
#include "swap.h"
using namespace std;
using ll = long long;

const int N = 3e5 + 5;

struct Edge {
  int u, v, w;
  Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
  bool operator < (const Edge& e) const {
    return w < e.w;
  }
} ed[N];

int n, m;

int lin[N], deg[N], ok[N], val[N];

int find(int i) {
  if (i == lin[i]) {
    return i;
  }
  return lin[i] = find(lin[i]);
}

vector<int> adj[N];

int unite(int u, int v, int w) {
  u = find(u); v = find(v);
  
  n++;
  lin[u] = lin[v] = lin[n] = n;
  val[n] = w;
  
  adj[n].emplace_back(u);
  ok[n] |= ok[u];

  if (u != v) {
    adj[n].emplace_back(v);
    ok[n] |= ok[v];
  } else {
    ok[n] = 1;
  }
  
  return n;
}

int dep[N], par[N][19];
void dfs(int u) {
  for (int v : adj[u]) {
    dep[v] = dep[u] + 1;
    par[v][0] = u; 
    for (int i = 1; i <= 18; ++i) {
      par[v][i] = par[par[v][i - 1]][i - 1];
    }
    dfs(v);
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  
  for (int i = 18; ~i; --i) {
    if (dep[par[u][i]] >= dep[v]) {
      u = par[u][i];
    }
  }
  
  if (u == v) {
    return u;
  }
  
  for (int i = 18; ~i; --i) {
    if (par[u][i] != par[v][i]) {
      u = par[u][i]; v = par[v][i];
    }
  }
  
  return par[u][0];
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N; m = M;
  for (int i = 1; i <= m; ++i) {
    int u = U[i - 1] + 1, v = V[i - 1] + 1, w = W[i - 1];
    ed[i] = {u, v, w};
  }
  
  sort(ed + 1, ed + m + 1);
  
  for (int i = 1; i <= n; ++i) {
    lin[i] = i;
  }
  
  for (int i = 1; i <= m; ++i) {
    deg[ed[i].u]++; deg[ed[i].v]++;
    int id = unite(ed[i].u, ed[i].v, ed[i].w);
    ok[id] |= deg[ed[i].u] >= 3 || deg[ed[i].v] >= 3;
  }
  
  int root = find(1);
  dfs(root);
  
}

int getMinimumFuelCapacity(int X, int Y) {
  int u = X + 1, v = Y + 1;

  int z = lca(u, v);
  if (ok[z]) {
    return val[z];
  }
  
  for (int i = 18; ~i; --i) {
    if (par[z][i] && !ok[par[z][i]]) {
      z = par[z][i];
    }
  }
  z = par[z][0];
  
  return ok[z] ? val[z] : -1;
}


// int main() {
  // int N, M;
  // assert(2 == scanf("%d %d", &N, &M));
//   
  // std::vector<int> U(M), V(M), W(M);
  // for (int i = 0; i < M; ++i) {
    // scanf("%d", &U[i]);
  // }
  // for (int i = 0; i < M; ++i) {
    // scanf("%d", &V[i]);
  // }
  // for (int i = 0; i < M; ++i) {
    // scanf("%d", &W[i]);
  // }
// 
  // int Q;
  // assert(1 == scanf("%d", &Q));
// 
  // std::vector<int> X(Q), Y(Q);
  // for (int i = 0; i < Q; ++i) {
    // scanf("%d %d ", &X[i], &Y[i]);
  // }
// 
  // init(N, M, U, V, W);
//   
  // std::vector<int> minimum_fuel_capacities(Q);
  // for (int i = 0; i < Q; ++i) {
    // minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  // }
// 
  // for (int i = 0; i < Q; ++i) {
    // printf("%d\n", minimum_fuel_capacities[i]);
  // }
//   
  // return 0;
// }

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 5 ms 10836 KB Output is correct
4 Correct 5 ms 10964 KB Output is correct
5 Correct 6 ms 11092 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 87 ms 29028 KB Output is correct
10 Correct 106 ms 32972 KB Output is correct
11 Correct 106 ms 32716 KB Output is correct
12 Correct 110 ms 33944 KB Output is correct
13 Correct 92 ms 37068 KB Output is correct
14 Correct 98 ms 29096 KB Output is correct
15 Correct 241 ms 34940 KB Output is correct
16 Correct 241 ms 34440 KB Output is correct
17 Correct 246 ms 35720 KB Output is correct
18 Correct 332 ms 38796 KB Output is correct
19 Correct 99 ms 17972 KB Output is correct
20 Correct 237 ms 36236 KB Output is correct
21 Correct 240 ms 35592 KB Output is correct
22 Correct 245 ms 37140 KB Output is correct
23 Correct 335 ms 40216 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 273 ms 41584 KB Output is correct
4 Correct 281 ms 43060 KB Output is correct
5 Correct 278 ms 42336 KB Output is correct
6 Correct 279 ms 46664 KB Output is correct
7 Correct 283 ms 46576 KB Output is correct
8 Correct 284 ms 45300 KB Output is correct
9 Correct 277 ms 46284 KB Output is correct
10 Correct 274 ms 45020 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 5 ms 10836 KB Output is correct
4 Correct 5 ms 10964 KB Output is correct
5 Correct 6 ms 11092 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 5 ms 10836 KB Output is correct
10 Correct 7 ms 11092 KB Output is correct
11 Correct 6 ms 11092 KB Output is correct
12 Correct 6 ms 11092 KB Output is correct
13 Correct 6 ms 11092 KB Output is correct
14 Correct 6 ms 11004 KB Output is correct
15 Correct 6 ms 11092 KB Output is correct
16 Correct 6 ms 11092 KB Output is correct
17 Correct 6 ms 11180 KB Output is correct
18 Correct 6 ms 11156 KB Output is correct
19 Correct 6 ms 11092 KB Output is correct
20 Correct 6 ms 11096 KB Output is correct
21 Correct 6 ms 11148 KB Output is correct
22 Correct 7 ms 11220 KB Output is correct
23 Correct 6 ms 11092 KB Output is correct
24 Correct 8 ms 11220 KB Output is correct
25 Correct 7 ms 11220 KB Output is correct
26 Correct 8 ms 11272 KB Output is correct
27 Correct 6 ms 11092 KB Output is correct
28 Correct 6 ms 11348 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10836 KB Output is correct
2 Correct 8 ms 10836 KB Output is correct
3 Correct 6 ms 10836 KB Output is correct
4 Correct 5 ms 10836 KB Output is correct
5 Correct 5 ms 10964 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 6 ms 11092 KB Output is correct
10 Correct 87 ms 29028 KB Output is correct
11 Correct 106 ms 32972 KB Output is correct
12 Correct 106 ms 32716 KB Output is correct
13 Correct 110 ms 33944 KB Output is correct
14 Correct 92 ms 37068 KB Output is correct
15 Correct 7 ms 11092 KB Output is correct
16 Correct 6 ms 11092 KB Output is correct
17 Correct 6 ms 11092 KB Output is correct
18 Correct 6 ms 11092 KB Output is correct
19 Correct 6 ms 11004 KB Output is correct
20 Correct 6 ms 11092 KB Output is correct
21 Correct 6 ms 11092 KB Output is correct
22 Correct 6 ms 11180 KB Output is correct
23 Correct 6 ms 11156 KB Output is correct
24 Correct 6 ms 11092 KB Output is correct
25 Correct 6 ms 11096 KB Output is correct
26 Correct 6 ms 11148 KB Output is correct
27 Correct 7 ms 11220 KB Output is correct
28 Correct 6 ms 11092 KB Output is correct
29 Correct 8 ms 11220 KB Output is correct
30 Correct 7 ms 11220 KB Output is correct
31 Correct 8 ms 11272 KB Output is correct
32 Correct 6 ms 11092 KB Output is correct
33 Correct 6 ms 11348 KB Output is correct
34 Correct 16 ms 14220 KB Output is correct
35 Correct 110 ms 35724 KB Output is correct
36 Correct 109 ms 35712 KB Output is correct
37 Correct 115 ms 35780 KB Output is correct
38 Correct 127 ms 35472 KB Output is correct
39 Correct 107 ms 35308 KB Output is correct
40 Correct 104 ms 33300 KB Output is correct
41 Correct 117 ms 35976 KB Output is correct
42 Correct 117 ms 35820 KB Output is correct
43 Correct 94 ms 39944 KB Output is correct
44 Correct 118 ms 36100 KB Output is correct
45 Correct 146 ms 47852 KB Output is correct
46 Correct 114 ms 35712 KB Output is correct
47 Correct 113 ms 35944 KB Output is correct
48 Correct 131 ms 39684 KB Output is correct
49 Correct 99 ms 46412 KB Output is correct
50 Correct 86 ms 38604 KB Output is correct
51 Correct 121 ms 42972 KB Output is correct
52 Correct 158 ms 50140 KB Output is correct
53 Correct 185 ms 52664 KB Output is correct
54 Correct 204 ms 58664 KB Output is correct
55 Correct 91 ms 39500 KB Output is correct
56 Correct 166 ms 54356 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10836 KB Output is correct
2 Correct 6 ms 10836 KB Output is correct
3 Correct 5 ms 10836 KB Output is correct
4 Correct 5 ms 10964 KB Output is correct
5 Correct 6 ms 11092 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 87 ms 29028 KB Output is correct
10 Correct 106 ms 32972 KB Output is correct
11 Correct 106 ms 32716 KB Output is correct
12 Correct 110 ms 33944 KB Output is correct
13 Correct 92 ms 37068 KB Output is correct
14 Correct 98 ms 29096 KB Output is correct
15 Correct 241 ms 34940 KB Output is correct
16 Correct 241 ms 34440 KB Output is correct
17 Correct 246 ms 35720 KB Output is correct
18 Correct 332 ms 38796 KB Output is correct
19 Correct 273 ms 41584 KB Output is correct
20 Correct 281 ms 43060 KB Output is correct
21 Correct 278 ms 42336 KB Output is correct
22 Correct 279 ms 46664 KB Output is correct
23 Correct 283 ms 46576 KB Output is correct
24 Correct 284 ms 45300 KB Output is correct
25 Correct 277 ms 46284 KB Output is correct
26 Correct 274 ms 45020 KB Output is correct
27 Correct 7 ms 11092 KB Output is correct
28 Correct 6 ms 11092 KB Output is correct
29 Correct 6 ms 11092 KB Output is correct
30 Correct 6 ms 11092 KB Output is correct
31 Correct 6 ms 11004 KB Output is correct
32 Correct 6 ms 11092 KB Output is correct
33 Correct 6 ms 11092 KB Output is correct
34 Correct 6 ms 11180 KB Output is correct
35 Correct 6 ms 11156 KB Output is correct
36 Correct 16 ms 14220 KB Output is correct
37 Correct 110 ms 35724 KB Output is correct
38 Correct 109 ms 35712 KB Output is correct
39 Correct 115 ms 35780 KB Output is correct
40 Correct 127 ms 35472 KB Output is correct
41 Correct 107 ms 35308 KB Output is correct
42 Correct 104 ms 33300 KB Output is correct
43 Correct 117 ms 35976 KB Output is correct
44 Correct 117 ms 35820 KB Output is correct
45 Correct 94 ms 39944 KB Output is correct
46 Correct 118 ms 36100 KB Output is correct
47 Correct 26 ms 14440 KB Output is correct
48 Correct 243 ms 40588 KB Output is correct
49 Correct 239 ms 40588 KB Output is correct
50 Correct 241 ms 40580 KB Output is correct
51 Correct 239 ms 40452 KB Output is correct
52 Correct 224 ms 39176 KB Output is correct
53 Correct 189 ms 33468 KB Output is correct
54 Correct 250 ms 41576 KB Output is correct
55 Correct 247 ms 40628 KB Output is correct
56 Correct 309 ms 43908 KB Output is correct
57 Correct 241 ms 41568 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10836 KB Output is correct
2 Correct 8 ms 10836 KB Output is correct
3 Correct 6 ms 10836 KB Output is correct
4 Correct 5 ms 10836 KB Output is correct
5 Correct 5 ms 10964 KB Output is correct
6 Correct 6 ms 11092 KB Output is correct
7 Correct 6 ms 11092 KB Output is correct
8 Correct 6 ms 11092 KB Output is correct
9 Correct 6 ms 11092 KB Output is correct
10 Correct 87 ms 29028 KB Output is correct
11 Correct 106 ms 32972 KB Output is correct
12 Correct 106 ms 32716 KB Output is correct
13 Correct 110 ms 33944 KB Output is correct
14 Correct 92 ms 37068 KB Output is correct
15 Correct 98 ms 29096 KB Output is correct
16 Correct 241 ms 34940 KB Output is correct
17 Correct 241 ms 34440 KB Output is correct
18 Correct 246 ms 35720 KB Output is correct
19 Correct 332 ms 38796 KB Output is correct
20 Correct 273 ms 41584 KB Output is correct
21 Correct 281 ms 43060 KB Output is correct
22 Correct 278 ms 42336 KB Output is correct
23 Correct 279 ms 46664 KB Output is correct
24 Correct 283 ms 46576 KB Output is correct
25 Correct 284 ms 45300 KB Output is correct
26 Correct 277 ms 46284 KB Output is correct
27 Correct 274 ms 45020 KB Output is correct
28 Correct 7 ms 11092 KB Output is correct
29 Correct 6 ms 11092 KB Output is correct
30 Correct 6 ms 11092 KB Output is correct
31 Correct 6 ms 11092 KB Output is correct
32 Correct 6 ms 11004 KB Output is correct
33 Correct 6 ms 11092 KB Output is correct
34 Correct 6 ms 11092 KB Output is correct
35 Correct 6 ms 11180 KB Output is correct
36 Correct 6 ms 11156 KB Output is correct
37 Correct 16 ms 14220 KB Output is correct
38 Correct 110 ms 35724 KB Output is correct
39 Correct 109 ms 35712 KB Output is correct
40 Correct 115 ms 35780 KB Output is correct
41 Correct 127 ms 35472 KB Output is correct
42 Correct 107 ms 35308 KB Output is correct
43 Correct 104 ms 33300 KB Output is correct
44 Correct 117 ms 35976 KB Output is correct
45 Correct 117 ms 35820 KB Output is correct
46 Correct 94 ms 39944 KB Output is correct
47 Correct 118 ms 36100 KB Output is correct
48 Correct 26 ms 14440 KB Output is correct
49 Correct 243 ms 40588 KB Output is correct
50 Correct 239 ms 40588 KB Output is correct
51 Correct 241 ms 40580 KB Output is correct
52 Correct 239 ms 40452 KB Output is correct
53 Correct 224 ms 39176 KB Output is correct
54 Correct 189 ms 33468 KB Output is correct
55 Correct 250 ms 41576 KB Output is correct
56 Correct 247 ms 40628 KB Output is correct
57 Correct 309 ms 43908 KB Output is correct
58 Correct 241 ms 41568 KB Output is correct
59 Correct 99 ms 17972 KB Output is correct
60 Correct 237 ms 36236 KB Output is correct
61 Correct 240 ms 35592 KB Output is correct
62 Correct 245 ms 37140 KB Output is correct
63 Correct 335 ms 40216 KB Output is correct
64 Correct 6 ms 11092 KB Output is correct
65 Correct 6 ms 11096 KB Output is correct
66 Correct 6 ms 11148 KB Output is correct
67 Correct 7 ms 11220 KB Output is correct
68 Correct 6 ms 11092 KB Output is correct
69 Correct 8 ms 11220 KB Output is correct
70 Correct 7 ms 11220 KB Output is correct
71 Correct 8 ms 11272 KB Output is correct
72 Correct 6 ms 11092 KB Output is correct
73 Correct 6 ms 11348 KB Output is correct
74 Correct 146 ms 47852 KB Output is correct
75 Correct 114 ms 35712 KB Output is correct
76 Correct 113 ms 35944 KB Output is correct
77 Correct 131 ms 39684 KB Output is correct
78 Correct 99 ms 46412 KB Output is correct
79 Correct 86 ms 38604 KB Output is correct
80 Correct 121 ms 42972 KB Output is correct
81 Correct 158 ms 50140 KB Output is correct
82 Correct 185 ms 52664 KB Output is correct
83 Correct 204 ms 58664 KB Output is correct
84 Correct 91 ms 39500 KB Output is correct
85 Correct 166 ms 54356 KB Output is correct
86 Correct 79 ms 24596 KB Output is correct
87 Correct 241 ms 40716 KB Output is correct
88 Correct 228 ms 40628 KB Output is correct
89 Correct 285 ms 43312 KB Output is correct
90 Correct 202 ms 52360 KB Output is correct
91 Correct 222 ms 49548 KB Output is correct
92 Correct 307 ms 46636 KB Output is correct
93 Correct 295 ms 54192 KB Output is correct
94 Correct 380 ms 57312 KB Output is correct
95 Correct 329 ms 62528 KB Output is correct
96 Correct 314 ms 44264 KB Output is correct
97 Correct 336 ms 50872 KB Output is correct