oj.uz

Submission #569738

# Submission time Handle Problem Language Result Execution time Memory
569738 2022-05-27T17:07:24 Z ryangohca Swapping Cities (APIO20_swap) C++17
30 / 100
 1308 ms 33260 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
int p[100001], pweight[100001][20], st[100001], en[100001], lineWeight[100001][20], twok[100001][20];
void init(int N){
    iota(p, p+N, 0);
    iota(st, st+N, 0);
    iota(en, en+N, 0);
    for (int i = 0; i < N; i++) lineWeight[i][0] = 2e9;
    memset(twok, -1, sizeof twok);
    memset(pweight, -1, sizeof pweight);
}
int fs(int x){
    if (p[x] == x) return x;
    return p[x] = fs(p[x]);
}
void ms(int x, int y, int w){
    int px = fs(x), py = fs(y);
    if (px == py){
        st[px] = en[px] = -1;
        lineWeight[px][0] = min(lineWeight[px][0], w);
        return;
    }
    p[py] = px; // px -> py
    //cout << px << ' ' << py << ' ' << w << endl;
    twok[py][0] = px;
    pweight[py][0] = w;
    if (st[px] != -1 && st[py] != -1){
        if ((st[px] == x || en[px] == x) && (st[py] == y || en[py] == y)){
            st[px] = (st[px] == x ? en[px] : st[px]);
            en[px] = (st[py] == y ? en[py] : st[py]);
        } else {
            st[px] = en[px] = -1;
            lineWeight[px][0] = min(lineWeight[px][0], w);
        }
    } else if (st[px] != -1){
        st[px] = en[px] = -1;
      	lineWeight[px][0] = w;
    } else {
        lineWeight[px][0] = min(lineWeight[px][0], lineWeight[py][0]);
    }
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    init(N);
    vector<tuple<int, int, int>> edges;
    for (int i = 0; i < M; i++){
        edges.push_back({W[i], U[i], V[i]});
    }
    sort(edges.begin(), edges.end());
    for (auto [w, a, b] : edges){
        ms(a, b, w);
    }
    for (int i = 1; i <= 19; i++){
        for (int j = 0; j < N; j++){
            if (twok[j][i-1] != -1){
                twok[j][i] = twok[twok[j][i-1]][i-1];
                pweight[j][i] = max(pweight[j][i-1], pweight[twok[j][i-1]][i-1]);
                lineWeight[j][i] = min(lineWeight[j][i-1], lineWeight[twok[j][i-1]][i-1]);
            }
        }
    }
}
bool isOkay(int mid, int X, int Y){
    int w = 2e9;
    for (int i = 19; i >= 0; i--){
        if (twok[X][i] != -1 && pweight[X][i] <= mid) {w = min(w, lineWeight[X][i]); X = twok[X][i];}
        if (twok[Y][i] != -1 && pweight[Y][i] <= mid) {w = min(w, lineWeight[Y][i]); Y = twok[Y][i];}
    }
    if (X != Y) return false;
    //cout << mid << ' ' << min(lineWeight[X][0], w) << endl;
    return min(lineWeight[X][0], w) <= mid;
}
int getMinimumFuelCapacity(int X, int Y) {
    int mini = 0, maxi = 1e9+10;
    while (maxi - mini > 1){
        int mid = (maxi + mini) / 2;
        if (isOkay(mid, X, Y)) maxi = mid;
        else mini = mid;
    }
    return (maxi==1e9+10?-1:maxi);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Correct 7 ms 16020 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 8 ms 16084 KB Output is correct
8 Correct 7 ms 16068 KB Output is correct
9 Correct 56 ms 27632 KB Output is correct
10 Correct 74 ms 29568 KB Output is correct
11 Correct 74 ms 29448 KB Output is correct
12 Correct 70 ms 30088 KB Output is correct
13 Correct 102 ms 30148 KB Output is correct
14 Correct 109 ms 27800 KB Output is correct
15 Correct 648 ms 32168 KB Output is correct
16 Correct 650 ms 31736 KB Output is correct
17 Correct 667 ms 32648 KB Output is correct
18 Correct 1286 ms 32528 KB Output is correct
19 Correct 403 ms 22432 KB Output is correct
20 Correct 621 ms 32164 KB Output is correct
21 Correct 649 ms 31792 KB Output is correct
22 Correct 688 ms 32592 KB Output is correct
23 Correct 1308 ms 32768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 502 ms 32252 KB Output is correct
4 Correct 500 ms 32076 KB Output is correct
5 Correct 508 ms 31756 KB Output is correct
6 Correct 447 ms 32092 KB Output is correct
7 Correct 509 ms 31928 KB Output is correct
8 Correct 517 ms 31352 KB Output is correct
9 Correct 505 ms 31736 KB Output is correct
10 Correct 517 ms 31416 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Correct 7 ms 16020 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 8 ms 16084 KB Output is correct
8 Correct 7 ms 16068 KB Output is correct
9 Correct 6 ms 15956 KB Output is correct
10 Correct 7 ms 16068 KB Output is correct
11 Correct 7 ms 16084 KB Output is correct
12 Correct 8 ms 16036 KB Output is correct
13 Correct 10 ms 16072 KB Output is correct
14 Correct 8 ms 16084 KB Output is correct
15 Correct 8 ms 16072 KB Output is correct
16 Correct 8 ms 16084 KB Output is correct
17 Correct 7 ms 16084 KB Output is correct
18 Correct 7 ms 16084 KB Output is correct
19 Correct 7 ms 16084 KB Output is correct
20 Correct 7 ms 16084 KB Output is correct
21 Correct 7 ms 16084 KB Output is correct
22 Correct 7 ms 16084 KB Output is correct
23 Correct 16 ms 16080 KB Output is correct
24 Correct 7 ms 16084 KB Output is correct
25 Correct 8 ms 16192 KB Output is correct
26 Correct 8 ms 16084 KB Output is correct
27 Correct 9 ms 16080 KB Output is correct
28 Correct 8 ms 16112 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 7 ms 16020 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 7 ms 16084 KB Output is correct
8 Correct 8 ms 16084 KB Output is correct
9 Correct 7 ms 16068 KB Output is correct
10 Correct 56 ms 27632 KB Output is correct
11 Correct 74 ms 29568 KB Output is correct
12 Correct 74 ms 29448 KB Output is correct
13 Correct 70 ms 30088 KB Output is correct
14 Correct 102 ms 30148 KB Output is correct
15 Correct 7 ms 16068 KB Output is correct
16 Correct 7 ms 16084 KB Output is correct
17 Correct 8 ms 16036 KB Output is correct
18 Correct 10 ms 16072 KB Output is correct
19 Correct 8 ms 16084 KB Output is correct
20 Correct 8 ms 16072 KB Output is correct
21 Correct 8 ms 16084 KB Output is correct
22 Correct 7 ms 16084 KB Output is correct
23 Correct 7 ms 16084 KB Output is correct
24 Correct 7 ms 16084 KB Output is correct
25 Correct 7 ms 16084 KB Output is correct
26 Correct 7 ms 16084 KB Output is correct
27 Correct 7 ms 16084 KB Output is correct
28 Correct 16 ms 16080 KB Output is correct
29 Correct 7 ms 16084 KB Output is correct
30 Correct 8 ms 16192 KB Output is correct
31 Correct 8 ms 16084 KB Output is correct
32 Correct 9 ms 16080 KB Output is correct
33 Correct 8 ms 16112 KB Output is correct
34 Correct 15 ms 18052 KB Output is correct
35 Correct 75 ms 29808 KB Output is correct
36 Correct 73 ms 29812 KB Output is correct
37 Correct 74 ms 29792 KB Output is correct
38 Correct 73 ms 29676 KB Output is correct
39 Correct 86 ms 29600 KB Output is correct
40 Correct 71 ms 28748 KB Output is correct
41 Correct 73 ms 29764 KB Output is correct
42 Correct 78 ms 29780 KB Output is correct
43 Correct 115 ms 29872 KB Output is correct
44 Correct 89 ms 29784 KB Output is correct
45 Correct 112 ms 30552 KB Output is correct
46 Correct 76 ms 29852 KB Output is correct
47 Correct 81 ms 29780 KB Output is correct
48 Correct 100 ms 29792 KB Output is correct
49 Correct 73 ms 23896 KB Output is correct
50 Correct 59 ms 21984 KB Output is correct
51 Correct 100 ms 27288 KB Output is correct
52 Correct 114 ms 32852 KB Output is correct
53 Incorrect 128 ms 33260 KB Output isn't correct
54 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 9 ms 15948 KB Output is correct
4 Correct 7 ms 16020 KB Output is correct
5 Correct 7 ms 16084 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 8 ms 16084 KB Output is correct
8 Correct 7 ms 16068 KB Output is correct
9 Correct 56 ms 27632 KB Output is correct
10 Correct 74 ms 29568 KB Output is correct
11 Correct 74 ms 29448 KB Output is correct
12 Correct 70 ms 30088 KB Output is correct
13 Correct 102 ms 30148 KB Output is correct
14 Correct 109 ms 27800 KB Output is correct
15 Correct 648 ms 32168 KB Output is correct
16 Correct 650 ms 31736 KB Output is correct
17 Correct 667 ms 32648 KB Output is correct
18 Correct 1286 ms 32528 KB Output is correct
19 Correct 502 ms 32252 KB Output is correct
20 Correct 500 ms 32076 KB Output is correct
21 Correct 508 ms 31756 KB Output is correct
22 Correct 447 ms 32092 KB Output is correct
23 Correct 509 ms 31928 KB Output is correct
24 Correct 517 ms 31352 KB Output is correct
25 Correct 505 ms 31736 KB Output is correct
26 Correct 517 ms 31416 KB Output is correct
27 Correct 7 ms 16068 KB Output is correct
28 Correct 7 ms 16084 KB Output is correct
29 Correct 8 ms 16036 KB Output is correct
30 Correct 10 ms 16072 KB Output is correct
31 Correct 8 ms 16084 KB Output is correct
32 Correct 8 ms 16072 KB Output is correct
33 Correct 8 ms 16084 KB Output is correct
34 Correct 7 ms 16084 KB Output is correct
35 Correct 7 ms 16084 KB Output is correct
36 Correct 15 ms 18052 KB Output is correct
37 Correct 75 ms 29808 KB Output is correct
38 Correct 73 ms 29812 KB Output is correct
39 Correct 74 ms 29792 KB Output is correct
40 Correct 73 ms 29676 KB Output is correct
41 Correct 86 ms 29600 KB Output is correct
42 Correct 71 ms 28748 KB Output is correct
43 Correct 73 ms 29764 KB Output is correct
44 Correct 78 ms 29780 KB Output is correct
45 Correct 115 ms 29872 KB Output is correct
46 Correct 89 ms 29784 KB Output is correct
47 Correct 79 ms 18224 KB Output is correct
48 Correct 627 ms 31332 KB Output is correct
49 Incorrect 645 ms 31404 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 9 ms 15948 KB Output is correct
5 Correct 7 ms 16020 KB Output is correct
6 Correct 7 ms 16084 KB Output is correct
7 Correct 7 ms 16084 KB Output is correct
8 Correct 8 ms 16084 KB Output is correct
9 Correct 7 ms 16068 KB Output is correct
10 Correct 56 ms 27632 KB Output is correct
11 Correct 74 ms 29568 KB Output is correct
12 Correct 74 ms 29448 KB Output is correct
13 Correct 70 ms 30088 KB Output is correct
14 Correct 102 ms 30148 KB Output is correct
15 Correct 109 ms 27800 KB Output is correct
16 Correct 648 ms 32168 KB Output is correct
17 Correct 650 ms 31736 KB Output is correct
18 Correct 667 ms 32648 KB Output is correct
19 Correct 1286 ms 32528 KB Output is correct
20 Correct 502 ms 32252 KB Output is correct
21 Correct 500 ms 32076 KB Output is correct
22 Correct 508 ms 31756 KB Output is correct
23 Correct 447 ms 32092 KB Output is correct
24 Correct 509 ms 31928 KB Output is correct
25 Correct 517 ms 31352 KB Output is correct
26 Correct 505 ms 31736 KB Output is correct
27 Correct 517 ms 31416 KB Output is correct
28 Correct 7 ms 16068 KB Output is correct
29 Correct 7 ms 16084 KB Output is correct
30 Correct 8 ms 16036 KB Output is correct
31 Correct 10 ms 16072 KB Output is correct
32 Correct 8 ms 16084 KB Output is correct
33 Correct 8 ms 16072 KB Output is correct
34 Correct 8 ms 16084 KB Output is correct
35 Correct 7 ms 16084 KB Output is correct
36 Correct 7 ms 16084 KB Output is correct
37 Correct 15 ms 18052 KB Output is correct
38 Correct 75 ms 29808 KB Output is correct
39 Correct 73 ms 29812 KB Output is correct
40 Correct 74 ms 29792 KB Output is correct
41 Correct 73 ms 29676 KB Output is correct
42 Correct 86 ms 29600 KB Output is correct
43 Correct 71 ms 28748 KB Output is correct
44 Correct 73 ms 29764 KB Output is correct
45 Correct 78 ms 29780 KB Output is correct
46 Correct 115 ms 29872 KB Output is correct
47 Correct 89 ms 29784 KB Output is correct
48 Correct 79 ms 18224 KB Output is correct
49 Correct 627 ms 31332 KB Output is correct
50 Incorrect 645 ms 31404 KB Output isn't correct
51 Halted 0 ms 0 KB -