oj.uz

Submission #349530

# Submission time Handle Problem Language Result Execution time Memory
349530 2021-01-17T18:39:02 Z parsabahrami Swapping Cities (APIO20_swap) C++17
100 / 100
 369 ms 43572 KB 
#include "swap.h"
#include <bits/stdc++.h>
#
using namespace std;

typedef long long int ll;
typedef pair<int, int > pii;

#define SZ(x)               (int) x.size()
#define F                   first
#define S                   second

const int N = 3e5 + 10;
int P[20][N], H[N], C[N], rt[N], D[N], M[N], tim;

int Find(int v) {
    return !rt[v] ? v : rt[v] = Find(rt[v]);
}

void Union(int u, int v, int w) {
    u = Find(u), v = Find(v);
    if (u == v) {
        ++tim;
        P[0][u] = rt[u] = P[0][tim] = tim;
        C[u] = w; M[tim] = 1;
    } else {
        ++tim;
        rt[u] = rt[v] = P[0][u] = P[0][v] = P[0][tim] = tim;
        C[u] = C[v] = w;
        M[tim] = M[u] | M[v];
    }
}

void init(int n, int m,
          vector<int> U, vector<int> V, vector<int> W) {
    tim = n - 1; vector<pair<int, pii>> E;
    for (int i = 0; i < m; i++) {
        E.push_back({W[i], {U[i], V[i]}});
    }
    sort(E.begin(), E.end());
    for (auto e : E) {
        int w = e.F, u = e.S.F, v = e.S.S;
        D[u]++, D[v]++;
        Union(u, v, w);
        if (D[u] > 2 || D[v] > 2) M[Find(u)] = 1;
    }
    for (int i = 1; i < 20; i++) for (int j = 0; j <= tim; j++) P[i][j] = P[i - 1][P[i - 1][j]];
    for (int i = tim - 1; i >= 0; i--) H[i] = H[P[0][i]] + 1;
}

int getMinimumFuelCapacity(int u, int v) {
    if (H[u] < H[v]) swap(u, v);
    for (int i = H[u] - H[v]; i; i -= i & -i) u = P[__builtin_ctz(i)][u];
    for (int i = 19; ~i; i--) {
        if (P[i][u] != P[i][v] || !M[P[i][v]]) {
            u = P[i][u], v = P[i][v];
        }
    }
    if (P[0][u] != P[0][v]) return -1;
    if (!M[P[0][u]]) return -1;
    return C[u];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 51 ms 18016 KB Output is correct
10 Correct 63 ms 21984 KB Output is correct
11 Correct 62 ms 21600 KB Output is correct
12 Correct 66 ms 22880 KB Output is correct
13 Correct 67 ms 24416 KB Output is correct
14 Correct 61 ms 18144 KB Output is correct
15 Correct 161 ms 23776 KB Output is correct
16 Correct 158 ms 23136 KB Output is correct
17 Correct 155 ms 24544 KB Output is correct
18 Correct 229 ms 26080 KB Output is correct
19 Correct 89 ms 7404 KB Output is correct
20 Correct 236 ms 23904 KB Output is correct
21 Correct 245 ms 23632 KB Output is correct
22 Correct 253 ms 24748 KB Output is correct
23 Correct 340 ms 26448 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 362 ms 23460 KB Output is correct
4 Correct 339 ms 24448 KB Output is correct
5 Correct 353 ms 23916 KB Output is correct
6 Correct 334 ms 24240 KB Output is correct
7 Correct 369 ms 24284 KB Output is correct
8 Correct 359 ms 23356 KB Output is correct
9 Correct 353 ms 24116 KB Output is correct
10 Correct 336 ms 23124 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 1 ms 620 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 2 ms 748 KB Output is correct
18 Correct 1 ms 748 KB Output is correct
19 Correct 1 ms 640 KB Output is correct
20 Correct 1 ms 748 KB Output is correct
21 Correct 1 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 1 ms 620 KB Output is correct
24 Correct 2 ms 748 KB Output is correct
25 Correct 2 ms 876 KB Output is correct
26 Correct 2 ms 876 KB Output is correct
27 Correct 1 ms 748 KB Output is correct
28 Correct 2 ms 876 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 51 ms 18016 KB Output is correct
11 Correct 63 ms 21984 KB Output is correct
12 Correct 62 ms 21600 KB Output is correct
13 Correct 66 ms 22880 KB Output is correct
14 Correct 67 ms 24416 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 620 KB Output is correct
19 Correct 1 ms 620 KB Output is correct
20 Correct 1 ms 748 KB Output is correct
21 Correct 1 ms 748 KB Output is correct
22 Correct 2 ms 748 KB Output is correct
23 Correct 1 ms 748 KB Output is correct
24 Correct 9 ms 3628 KB Output is correct
25 Correct 62 ms 22880 KB Output is correct
26 Correct 62 ms 22880 KB Output is correct
27 Correct 63 ms 22880 KB Output is correct
28 Correct 62 ms 22516 KB Output is correct
29 Correct 63 ms 22528 KB Output is correct
30 Correct 57 ms 20576 KB Output is correct
31 Correct 65 ms 22880 KB Output is correct
32 Correct 62 ms 22880 KB Output is correct
33 Correct 62 ms 22880 KB Output is correct
34 Correct 68 ms 22880 KB Output is correct
35 Correct 1 ms 640 KB Output is correct
36 Correct 1 ms 748 KB Output is correct
37 Correct 1 ms 748 KB Output is correct
38 Correct 2 ms 748 KB Output is correct
39 Correct 1 ms 620 KB Output is correct
40 Correct 2 ms 748 KB Output is correct
41 Correct 2 ms 876 KB Output is correct
42 Correct 2 ms 876 KB Output is correct
43 Correct 1 ms 748 KB Output is correct
44 Correct 2 ms 876 KB Output is correct
45 Correct 109 ms 26972 KB Output is correct
46 Correct 63 ms 24672 KB Output is correct
47 Correct 65 ms 24672 KB Output is correct
48 Correct 78 ms 26080 KB Output is correct
49 Correct 100 ms 23900 KB Output is correct
50 Correct 81 ms 19168 KB Output is correct
51 Correct 94 ms 25824 KB Output is correct
52 Correct 116 ms 34396 KB Output is correct
53 Correct 125 ms 36828 KB Output is correct
54 Correct 145 ms 39640 KB Output is correct
55 Correct 63 ms 24672 KB Output is correct
56 Correct 128 ms 35804 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 51 ms 18016 KB Output is correct
10 Correct 63 ms 21984 KB Output is correct
11 Correct 62 ms 21600 KB Output is correct
12 Correct 66 ms 22880 KB Output is correct
13 Correct 67 ms 24416 KB Output is correct
14 Correct 61 ms 18144 KB Output is correct
15 Correct 161 ms 23776 KB Output is correct
16 Correct 158 ms 23136 KB Output is correct
17 Correct 155 ms 24544 KB Output is correct
18 Correct 229 ms 26080 KB Output is correct
19 Correct 362 ms 23460 KB Output is correct
20 Correct 339 ms 24448 KB Output is correct
21 Correct 353 ms 23916 KB Output is correct
22 Correct 334 ms 24240 KB Output is correct
23 Correct 369 ms 24284 KB Output is correct
24 Correct 359 ms 23356 KB Output is correct
25 Correct 353 ms 24116 KB Output is correct
26 Correct 336 ms 23124 KB Output is correct
27 Correct 1 ms 748 KB Output is correct
28 Correct 1 ms 748 KB Output is correct
29 Correct 1 ms 748 KB Output is correct
30 Correct 1 ms 620 KB Output is correct
31 Correct 1 ms 620 KB Output is correct
32 Correct 1 ms 748 KB Output is correct
33 Correct 1 ms 748 KB Output is correct
34 Correct 2 ms 748 KB Output is correct
35 Correct 1 ms 748 KB Output is correct
36 Correct 9 ms 3628 KB Output is correct
37 Correct 62 ms 22880 KB Output is correct
38 Correct 62 ms 22880 KB Output is correct
39 Correct 63 ms 22880 KB Output is correct
40 Correct 62 ms 22516 KB Output is correct
41 Correct 63 ms 22528 KB Output is correct
42 Correct 57 ms 20576 KB Output is correct
43 Correct 65 ms 22880 KB Output is correct
44 Correct 62 ms 22880 KB Output is correct
45 Correct 62 ms 22880 KB Output is correct
46 Correct 68 ms 22880 KB Output is correct
47 Correct 19 ms 3608 KB Output is correct
48 Correct 252 ms 24580 KB Output is correct
49 Correct 248 ms 24544 KB Output is correct
50 Correct 243 ms 24416 KB Output is correct
51 Correct 241 ms 24288 KB Output is correct
52 Correct 237 ms 23008 KB Output is correct
53 Correct 208 ms 17988 KB Output is correct
54 Correct 256 ms 24972 KB Output is correct
55 Correct 256 ms 24416 KB Output is correct
56 Correct 359 ms 24544 KB Output is correct
57 Correct 251 ms 24748 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 51 ms 18016 KB Output is correct
11 Correct 63 ms 21984 KB Output is correct
12 Correct 62 ms 21600 KB Output is correct
13 Correct 66 ms 22880 KB Output is correct
14 Correct 67 ms 24416 KB Output is correct
15 Correct 61 ms 18144 KB Output is correct
16 Correct 161 ms 23776 KB Output is correct
17 Correct 158 ms 23136 KB Output is correct
18 Correct 155 ms 24544 KB Output is correct
19 Correct 229 ms 26080 KB Output is correct
20 Correct 362 ms 23460 KB Output is correct
21 Correct 339 ms 24448 KB Output is correct
22 Correct 353 ms 23916 KB Output is correct
23 Correct 334 ms 24240 KB Output is correct
24 Correct 369 ms 24284 KB Output is correct
25 Correct 359 ms 23356 KB Output is correct
26 Correct 353 ms 24116 KB Output is correct
27 Correct 336 ms 23124 KB Output is correct
28 Correct 1 ms 748 KB Output is correct
29 Correct 1 ms 748 KB Output is correct
30 Correct 1 ms 748 KB Output is correct
31 Correct 1 ms 620 KB Output is correct
32 Correct 1 ms 620 KB Output is correct
33 Correct 1 ms 748 KB Output is correct
34 Correct 1 ms 748 KB Output is correct
35 Correct 2 ms 748 KB Output is correct
36 Correct 1 ms 748 KB Output is correct
37 Correct 9 ms 3628 KB Output is correct
38 Correct 62 ms 22880 KB Output is correct
39 Correct 62 ms 22880 KB Output is correct
40 Correct 63 ms 22880 KB Output is correct
41 Correct 62 ms 22516 KB Output is correct
42 Correct 63 ms 22528 KB Output is correct
43 Correct 57 ms 20576 KB Output is correct
44 Correct 65 ms 22880 KB Output is correct
45 Correct 62 ms 22880 KB Output is correct
46 Correct 62 ms 22880 KB Output is correct
47 Correct 68 ms 22880 KB Output is correct
48 Correct 19 ms 3608 KB Output is correct
49 Correct 252 ms 24580 KB Output is correct
50 Correct 248 ms 24544 KB Output is correct
51 Correct 243 ms 24416 KB Output is correct
52 Correct 241 ms 24288 KB Output is correct
53 Correct 237 ms 23008 KB Output is correct
54 Correct 208 ms 17988 KB Output is correct
55 Correct 256 ms 24972 KB Output is correct
56 Correct 256 ms 24416 KB Output is correct
57 Correct 359 ms 24544 KB Output is correct
58 Correct 251 ms 24748 KB Output is correct
59 Correct 89 ms 7404 KB Output is correct
60 Correct 236 ms 23904 KB Output is correct
61 Correct 245 ms 23632 KB Output is correct
62 Correct 253 ms 24748 KB Output is correct
63 Correct 340 ms 26448 KB Output is correct
64 Correct 1 ms 640 KB Output is correct
65 Correct 1 ms 748 KB Output is correct
66 Correct 1 ms 748 KB Output is correct
67 Correct 2 ms 748 KB Output is correct
68 Correct 1 ms 620 KB Output is correct
69 Correct 2 ms 748 KB Output is correct
70 Correct 2 ms 876 KB Output is correct
71 Correct 2 ms 876 KB Output is correct
72 Correct 1 ms 748 KB Output is correct
73 Correct 2 ms 876 KB Output is correct
74 Correct 109 ms 26972 KB Output is correct
75 Correct 63 ms 24672 KB Output is correct
76 Correct 65 ms 24672 KB Output is correct
77 Correct 78 ms 26080 KB Output is correct
78 Correct 100 ms 23900 KB Output is correct
79 Correct 81 ms 19168 KB Output is correct
80 Correct 94 ms 25824 KB Output is correct
81 Correct 116 ms 34396 KB Output is correct
82 Correct 125 ms 36828 KB Output is correct
83 Correct 145 ms 39640 KB Output is correct
84 Correct 63 ms 24672 KB Output is correct
85 Correct 128 ms 35804 KB Output is correct
86 Correct 80 ms 12004 KB Output is correct
87 Correct 232 ms 28768 KB Output is correct
88 Correct 234 ms 28512 KB Output is correct
89 Correct 316 ms 28640 KB Output is correct
90 Correct 200 ms 28636 KB Output is correct
91 Correct 220 ms 27352 KB Output is correct
92 Correct 309 ms 28768 KB Output is correct
93 Correct 291 ms 37720 KB Output is correct
94 Correct 343 ms 40412 KB Output is correct
95 Correct 329 ms 43572 KB Output is correct
96 Correct 345 ms 28640 KB Output is correct
97 Correct 366 ms 34264 KB Output is correct