oj.uz

Submission #777881

# Submission time Handle Problem Language Result Execution time Memory
777881 2023-07-09T20:57:07 Z t6twotwo Swapping Cities (APIO20_swap) C++17
37 / 100
 2000 ms 27984 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
int N, M;
vector<int> ans, dep, p, up, w, f;
int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}
vector<vector<int>> par;
constexpr int inf = 2e9;
void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    N = n;
    M = m;
    p.resize(N + M);
    iota(p.begin(), p.end(), 0);
    vector<int> dif(N + M, -1), three(N + M), deg(N);
    w.resize(N + M);
    vector<vector<int>> ch(N + M);
    auto unite = [&](int x, int y, int t) {
        x = find(x);
        y = find(y);
        dif[t] = 1;
        for (int z : set<int>{x, y}) {
            three[t] |= three[z];
            dif[t] += dif[z];
            p[z] = t;
            up[z] = t;
            ch[t].push_back(z);
        }
    };
    vector<tuple<int, int, int>> edges(M);
    for (int i = 0; i < M; i++) {
        edges[i] = {W[i], U[i], V[i]};
    }
    sort(edges.begin(), edges.end());
    f.resize(N + M);
    up.resize(N + M, -1);
    for (int i = 0; i < M; i++) {
        auto [z, x, y] = edges[i];
        if (++deg[x] == 3) {
            three[find(x)] = 1;
        }
        if (++deg[y] == 3) {
            three[find(y)] = 1;
        }
        w[N + i] = z;
        unite(x, y, N + i);
        f[N + i] = three[N + i] == 1 || dif[N + i] >= 0;
    }
}
int getMinimumFuelCapacity(int x, int y) {
    if (find(x) != find(y)) {
        return -1;
    }
    while (x != y) {
        if (x < y) {
            x = up[x];
        } else {
            y = up[y];
        }
    }
    int ans = inf;
    while (x != -1) {
        if (f[x]) {
            ans = min(ans, w[x]);
        }
        x = up[x];
    }
    if (ans == inf) {
        ans = -1;
    }
    return ans;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 43 ms 13104 KB Output is correct
10 Correct 50 ms 16080 KB Output is correct
11 Correct 49 ms 15744 KB Output is correct
12 Correct 52 ms 16668 KB Output is correct
13 Correct 51 ms 17344 KB Output is correct
14 Correct 51 ms 13256 KB Output is correct
15 Correct 144 ms 18992 KB Output is correct
16 Correct 143 ms 18556 KB Output is correct
17 Correct 151 ms 19608 KB Output is correct
18 Execution timed out 2017 ms 20128 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Execution timed out 2069 ms 17264 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 43 ms 13104 KB Output is correct
11 Correct 50 ms 16080 KB Output is correct
12 Correct 49 ms 15744 KB Output is correct
13 Correct 52 ms 16668 KB Output is correct
14 Correct 51 ms 17344 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 468 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 7 ms 2420 KB Output is correct
35 Correct 53 ms 16708 KB Output is correct
36 Correct 59 ms 16716 KB Output is correct
37 Correct 53 ms 16784 KB Output is correct
38 Correct 50 ms 16440 KB Output is correct
39 Correct 49 ms 16332 KB Output is correct
40 Correct 46 ms 15016 KB Output is correct
41 Correct 52 ms 16716 KB Output is correct
42 Correct 50 ms 16684 KB Output is correct
43 Correct 49 ms 16716 KB Output is correct
44 Correct 53 ms 16708 KB Output is correct
45 Correct 97 ms 20912 KB Output is correct
46 Correct 50 ms 16732 KB Output is correct
47 Correct 54 ms 16604 KB Output is correct
48 Correct 59 ms 17772 KB Output is correct
49 Correct 70 ms 18296 KB Output is correct
50 Correct 58 ms 14336 KB Output is correct
51 Correct 71 ms 18060 KB Output is correct
52 Correct 88 ms 23628 KB Output is correct
53 Correct 91 ms 25704 KB Output is correct
54 Correct 106 ms 27984 KB Output is correct
55 Correct 49 ms 16716 KB Output is correct
56 Correct 94 ms 24772 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 43 ms 13104 KB Output is correct
10 Correct 50 ms 16080 KB Output is correct
11 Correct 49 ms 15744 KB Output is correct
12 Correct 52 ms 16668 KB Output is correct
13 Correct 51 ms 17344 KB Output is correct
14 Correct 51 ms 13256 KB Output is correct
15 Correct 144 ms 18992 KB Output is correct
16 Correct 143 ms 18556 KB Output is correct
17 Correct 151 ms 19608 KB Output is correct
18 Execution timed out 2017 ms 20128 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 43 ms 13104 KB Output is correct
11 Correct 50 ms 16080 KB Output is correct
12 Correct 49 ms 15744 KB Output is correct
13 Correct 52 ms 16668 KB Output is correct
14 Correct 51 ms 17344 KB Output is correct
15 Correct 51 ms 13256 KB Output is correct
16 Correct 144 ms 18992 KB Output is correct
17 Correct 143 ms 18556 KB Output is correct
18 Correct 151 ms 19608 KB Output is correct
19 Execution timed out 2017 ms 20128 KB Time limit exceeded
20 Halted 0 ms 0 KB -