oj.uz

Submission #429181

# Submission time Handle Problem Language Result Execution time Memory
429181 2021-06-15T18:21:05 Z Hegdahl Swapping Cities (APIO20_swap) C++17
100 / 100
 552 ms 42356 KB 
#include "swap.h"
#include <bits/stdc++.h>
#define ar array

using namespace std;

const int mxN = 4*2e5;

int deg[mxN], boss[mxN], lk[mxN], rk[mxN], ndw[mxN], can_pass[mxN], nxt;

int find(int i) {
  return i == boss[i] ? i : boss[i] = find(boss[i]);
}

void unite(int i, int j, int w) {
  bool tri = ++deg[i] >= 3 || ++deg[j] >= 3;

  i = find(i), j = find(j);
  if (i == j) {
    if (can_pass[i]) return;
    lk[nxt] = i;
    can_pass[nxt] = 1;
    ndw[nxt] = w;
    boss[i] = nxt++;
    return;
  }

  lk[nxt] = i;
  rk[nxt] = j;
  can_pass[nxt] = tri || can_pass[i] || can_pass[j];
  ndw[nxt] = w;
  boss[i] = boss[j] = nxt++;
}

int up[mxN][20], depth[mxN];
void dfs(int cur, int prv, int d) {
  depth[cur] = d;
  up[cur][0] = prv;
  for (int lvl = 0; lvl < 19; ++lvl)
    up[cur][lvl+1] = up[up[cur][lvl]][lvl];

  if (lk[cur] != -1) dfs(lk[cur], cur, d+1);
  if (rk[cur] != -1) dfs(rk[cur], cur, d+1);
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
  iota(boss, boss+mxN, 0);
  fill(lk, lk+mxN, -1);
  fill(rk, rk+mxN, -1);
  nxt = n;

  vector<int> s(m);
  iota(s.begin(), s.end(), 0);
  sort(s.begin(), s.end(), [&](int i, int j) { return w[i] < w[j]; });
  for (int i : s) unite(u[i], v[i], w[i]);

  for (int i = 1; i < n; ++i)
    assert(find(i) == find(0));

  dfs(find(0), find(0), 0);
}

int getMinimumFuelCapacity(int i, int j) {
  if (depth[i] > depth[j]) swap(i, j);

  for (int lvl = 19; lvl >= 0; --lvl)
    if (depth[up[j][lvl]] >= depth[i])
      j = up[j][lvl];

  for (int lvl = 19; lvl >= 0; --lvl)
    if (up[i][lvl] != up[j][lvl])
      i = up[i][lvl], j = up[j][lvl];

  if (i != j) i = up[i][0], j = up[j][0];

  assert(i == j);

  for (int lvl = 19; lvl >= 0; --lvl)
    if (!can_pass[up[i][lvl]])
      i = up[i][lvl];

  if (!can_pass[i]) i = up[i][0];

  if (!can_pass[i]) return -1;

  return ndw[i];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9640 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 6 ms 9932 KB Output is correct
6 Correct 7 ms 9864 KB Output is correct
7 Correct 6 ms 9932 KB Output is correct
8 Correct 6 ms 9932 KB Output is correct
9 Correct 76 ms 27324 KB Output is correct
10 Correct 93 ms 31284 KB Output is correct
11 Correct 101 ms 30968 KB Output is correct
12 Correct 102 ms 32196 KB Output is correct
13 Correct 99 ms 33712 KB Output is correct
14 Correct 91 ms 27568 KB Output is correct
15 Correct 299 ms 35012 KB Output is correct
16 Correct 286 ms 34472 KB Output is correct
17 Correct 304 ms 35768 KB Output is correct
18 Correct 412 ms 37320 KB Output is correct
19 Correct 134 ms 18244 KB Output is correct
20 Correct 278 ms 36184 KB Output is correct
21 Correct 289 ms 35760 KB Output is correct
22 Correct 300 ms 37200 KB Output is correct
23 Correct 552 ms 38768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 432 ms 40908 KB Output is correct
4 Correct 414 ms 42120 KB Output is correct
5 Correct 421 ms 41764 KB Output is correct
6 Correct 445 ms 41924 KB Output is correct
7 Correct 419 ms 41988 KB Output is correct
8 Correct 417 ms 40848 KB Output is correct
9 Correct 455 ms 41620 KB Output is correct
10 Correct 433 ms 40624 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9640 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 6 ms 9932 KB Output is correct
6 Correct 7 ms 9864 KB Output is correct
7 Correct 6 ms 9932 KB Output is correct
8 Correct 6 ms 9932 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9868 KB Output is correct
11 Correct 7 ms 9932 KB Output is correct
12 Correct 6 ms 9932 KB Output is correct
13 Correct 7 ms 9804 KB Output is correct
14 Correct 6 ms 9804 KB Output is correct
15 Correct 6 ms 9932 KB Output is correct
16 Correct 6 ms 9912 KB Output is correct
17 Correct 6 ms 9936 KB Output is correct
18 Correct 6 ms 9932 KB Output is correct
19 Correct 6 ms 9804 KB Output is correct
20 Correct 7 ms 9932 KB Output is correct
21 Correct 7 ms 9856 KB Output is correct
22 Correct 6 ms 9928 KB Output is correct
23 Correct 6 ms 9780 KB Output is correct
24 Correct 6 ms 9932 KB Output is correct
25 Correct 6 ms 9956 KB Output is correct
26 Correct 6 ms 9908 KB Output is correct
27 Correct 6 ms 9908 KB Output is correct
28 Correct 7 ms 9920 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9640 KB Output is correct
5 Correct 6 ms 9804 KB Output is correct
6 Correct 6 ms 9932 KB Output is correct
7 Correct 7 ms 9864 KB Output is correct
8 Correct 6 ms 9932 KB Output is correct
9 Correct 6 ms 9932 KB Output is correct
10 Correct 76 ms 27324 KB Output is correct
11 Correct 93 ms 31284 KB Output is correct
12 Correct 101 ms 30968 KB Output is correct
13 Correct 102 ms 32196 KB Output is correct
14 Correct 99 ms 33712 KB Output is correct
15 Correct 6 ms 9868 KB Output is correct
16 Correct 7 ms 9932 KB Output is correct
17 Correct 6 ms 9932 KB Output is correct
18 Correct 7 ms 9804 KB Output is correct
19 Correct 6 ms 9804 KB Output is correct
20 Correct 6 ms 9932 KB Output is correct
21 Correct 6 ms 9912 KB Output is correct
22 Correct 6 ms 9936 KB Output is correct
23 Correct 6 ms 9932 KB Output is correct
24 Correct 6 ms 9804 KB Output is correct
25 Correct 7 ms 9932 KB Output is correct
26 Correct 7 ms 9856 KB Output is correct
27 Correct 6 ms 9928 KB Output is correct
28 Correct 6 ms 9780 KB Output is correct
29 Correct 6 ms 9932 KB Output is correct
30 Correct 6 ms 9956 KB Output is correct
31 Correct 6 ms 9908 KB Output is correct
32 Correct 6 ms 9908 KB Output is correct
33 Correct 7 ms 9920 KB Output is correct
34 Correct 15 ms 12716 KB Output is correct
35 Correct 102 ms 31812 KB Output is correct
36 Correct 97 ms 31812 KB Output is correct
37 Correct 100 ms 31928 KB Output is correct
38 Correct 95 ms 31468 KB Output is correct
39 Correct 108 ms 31428 KB Output is correct
40 Correct 89 ms 29588 KB Output is correct
41 Correct 99 ms 32184 KB Output is correct
42 Correct 92 ms 31800 KB Output is correct
43 Correct 98 ms 33844 KB Output is correct
44 Correct 101 ms 32296 KB Output is correct
45 Correct 117 ms 31428 KB Output is correct
46 Correct 94 ms 31796 KB Output is correct
47 Correct 116 ms 31796 KB Output is correct
48 Correct 129 ms 32708 KB Output is correct
49 Correct 79 ms 16964 KB Output is correct
50 Correct 64 ms 16660 KB Output is correct
51 Correct 100 ms 27716 KB Output is correct
52 Correct 158 ms 35184 KB Output is correct
53 Correct 193 ms 39364 KB Output is correct
54 Correct 155 ms 36672 KB Output is correct
55 Correct 100 ms 33708 KB Output is correct
56 Correct 164 ms 36580 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9640 KB Output is correct
4 Correct 6 ms 9804 KB Output is correct
5 Correct 6 ms 9932 KB Output is correct
6 Correct 7 ms 9864 KB Output is correct
7 Correct 6 ms 9932 KB Output is correct
8 Correct 6 ms 9932 KB Output is correct
9 Correct 76 ms 27324 KB Output is correct
10 Correct 93 ms 31284 KB Output is correct
11 Correct 101 ms 30968 KB Output is correct
12 Correct 102 ms 32196 KB Output is correct
13 Correct 99 ms 33712 KB Output is correct
14 Correct 91 ms 27568 KB Output is correct
15 Correct 299 ms 35012 KB Output is correct
16 Correct 286 ms 34472 KB Output is correct
17 Correct 304 ms 35768 KB Output is correct
18 Correct 412 ms 37320 KB Output is correct
19 Correct 432 ms 40908 KB Output is correct
20 Correct 414 ms 42120 KB Output is correct
21 Correct 421 ms 41764 KB Output is correct
22 Correct 445 ms 41924 KB Output is correct
23 Correct 419 ms 41988 KB Output is correct
24 Correct 417 ms 40848 KB Output is correct
25 Correct 455 ms 41620 KB Output is correct
26 Correct 433 ms 40624 KB Output is correct
27 Correct 6 ms 9868 KB Output is correct
28 Correct 7 ms 9932 KB Output is correct
29 Correct 6 ms 9932 KB Output is correct
30 Correct 7 ms 9804 KB Output is correct
31 Correct 6 ms 9804 KB Output is correct
32 Correct 6 ms 9932 KB Output is correct
33 Correct 6 ms 9912 KB Output is correct
34 Correct 6 ms 9936 KB Output is correct
35 Correct 6 ms 9932 KB Output is correct
36 Correct 15 ms 12716 KB Output is correct
37 Correct 102 ms 31812 KB Output is correct
38 Correct 97 ms 31812 KB Output is correct
39 Correct 100 ms 31928 KB Output is correct
40 Correct 95 ms 31468 KB Output is correct
41 Correct 108 ms 31428 KB Output is correct
42 Correct 89 ms 29588 KB Output is correct
43 Correct 99 ms 32184 KB Output is correct
44 Correct 92 ms 31800 KB Output is correct
45 Correct 98 ms 33844 KB Output is correct
46 Correct 101 ms 32296 KB Output is correct
47 Correct 30 ms 12832 KB Output is correct
48 Correct 368 ms 36284 KB Output is correct
49 Correct 284 ms 36372 KB Output is correct
50 Correct 375 ms 36232 KB Output is correct
51 Correct 328 ms 36176 KB Output is correct
52 Correct 268 ms 34984 KB Output is correct
53 Correct 256 ms 30120 KB Output is correct
54 Correct 293 ms 37200 KB Output is correct
55 Correct 340 ms 36280 KB Output is correct
56 Correct 455 ms 37916 KB Output is correct
57 Correct 281 ms 37252 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 5 ms 9676 KB Output is correct
3 Correct 5 ms 9676 KB Output is correct
4 Correct 5 ms 9640 KB Output is correct
5 Correct 6 ms 9804 KB Output is correct
6 Correct 6 ms 9932 KB Output is correct
7 Correct 7 ms 9864 KB Output is correct
8 Correct 6 ms 9932 KB Output is correct
9 Correct 6 ms 9932 KB Output is correct
10 Correct 76 ms 27324 KB Output is correct
11 Correct 93 ms 31284 KB Output is correct
12 Correct 101 ms 30968 KB Output is correct
13 Correct 102 ms 32196 KB Output is correct
14 Correct 99 ms 33712 KB Output is correct
15 Correct 91 ms 27568 KB Output is correct
16 Correct 299 ms 35012 KB Output is correct
17 Correct 286 ms 34472 KB Output is correct
18 Correct 304 ms 35768 KB Output is correct
19 Correct 412 ms 37320 KB Output is correct
20 Correct 432 ms 40908 KB Output is correct
21 Correct 414 ms 42120 KB Output is correct
22 Correct 421 ms 41764 KB Output is correct
23 Correct 445 ms 41924 KB Output is correct
24 Correct 419 ms 41988 KB Output is correct
25 Correct 417 ms 40848 KB Output is correct
26 Correct 455 ms 41620 KB Output is correct
27 Correct 433 ms 40624 KB Output is correct
28 Correct 6 ms 9868 KB Output is correct
29 Correct 7 ms 9932 KB Output is correct
30 Correct 6 ms 9932 KB Output is correct
31 Correct 7 ms 9804 KB Output is correct
32 Correct 6 ms 9804 KB Output is correct
33 Correct 6 ms 9932 KB Output is correct
34 Correct 6 ms 9912 KB Output is correct
35 Correct 6 ms 9936 KB Output is correct
36 Correct 6 ms 9932 KB Output is correct
37 Correct 15 ms 12716 KB Output is correct
38 Correct 102 ms 31812 KB Output is correct
39 Correct 97 ms 31812 KB Output is correct
40 Correct 100 ms 31928 KB Output is correct
41 Correct 95 ms 31468 KB Output is correct
42 Correct 108 ms 31428 KB Output is correct
43 Correct 89 ms 29588 KB Output is correct
44 Correct 99 ms 32184 KB Output is correct
45 Correct 92 ms 31800 KB Output is correct
46 Correct 98 ms 33844 KB Output is correct
47 Correct 101 ms 32296 KB Output is correct
48 Correct 30 ms 12832 KB Output is correct
49 Correct 368 ms 36284 KB Output is correct
50 Correct 284 ms 36372 KB Output is correct
51 Correct 375 ms 36232 KB Output is correct
52 Correct 328 ms 36176 KB Output is correct
53 Correct 268 ms 34984 KB Output is correct
54 Correct 256 ms 30120 KB Output is correct
55 Correct 293 ms 37200 KB Output is correct
56 Correct 340 ms 36280 KB Output is correct
57 Correct 455 ms 37916 KB Output is correct
58 Correct 281 ms 37252 KB Output is correct
59 Correct 134 ms 18244 KB Output is correct
60 Correct 278 ms 36184 KB Output is correct
61 Correct 289 ms 35760 KB Output is correct
62 Correct 300 ms 37200 KB Output is correct
63 Correct 552 ms 38768 KB Output is correct
64 Correct 6 ms 9804 KB Output is correct
65 Correct 7 ms 9932 KB Output is correct
66 Correct 7 ms 9856 KB Output is correct
67 Correct 6 ms 9928 KB Output is correct
68 Correct 6 ms 9780 KB Output is correct
69 Correct 6 ms 9932 KB Output is correct
70 Correct 6 ms 9956 KB Output is correct
71 Correct 6 ms 9908 KB Output is correct
72 Correct 6 ms 9908 KB Output is correct
73 Correct 7 ms 9920 KB Output is correct
74 Correct 117 ms 31428 KB Output is correct
75 Correct 94 ms 31796 KB Output is correct
76 Correct 116 ms 31796 KB Output is correct
77 Correct 129 ms 32708 KB Output is correct
78 Correct 79 ms 16964 KB Output is correct
79 Correct 64 ms 16660 KB Output is correct
80 Correct 100 ms 27716 KB Output is correct
81 Correct 158 ms 35184 KB Output is correct
82 Correct 193 ms 39364 KB Output is correct
83 Correct 155 ms 36672 KB Output is correct
84 Correct 100 ms 33708 KB Output is correct
85 Correct 164 ms 36580 KB Output is correct
86 Correct 86 ms 18796 KB Output is correct
87 Correct 271 ms 36392 KB Output is correct
88 Correct 345 ms 36520 KB Output is correct
89 Correct 374 ms 35788 KB Output is correct
90 Correct 219 ms 20928 KB Output is correct
91 Correct 290 ms 22604 KB Output is correct
92 Correct 362 ms 32188 KB Output is correct
93 Correct 318 ms 39204 KB Output is correct
94 Correct 439 ms 42356 KB Output is correct
95 Correct 370 ms 40652 KB Output is correct
96 Correct 500 ms 38148 KB Output is correct
97 Correct 370 ms 39228 KB Output is correct