oj.uz

Submission #569739

# Submission time Handle Problem Language Result Execution time Memory
569739 2022-05-27T17:11:19 Z ryangohca Swapping Cities (APIO20_swap) C++17
0 / 100
 1229 ms 30532 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] = max(lineWeight[j][i-1], lineWeight[twok[j][i-1]][i-1]);
            }
        }
    }
}
bool isOkay(int mid, int X, int Y){
    int w = 0;
    for (int i = 19; i >= 0; i--){
        if (twok[X][i] != -1 && pweight[X][i] <= mid) {w = max(w, lineWeight[X][i]); X = twok[X][i];}
        if (twok[Y][i] != -1 && pweight[Y][i] <= mid) {w = max(w, lineWeight[Y][i]); Y = twok[Y][i];}
    }
    if (X != Y) return false;
    //cout << mid << ' ' << min(lineWeight[X][0], w) << endl;
    return max(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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15868 KB Output is correct
3 Correct 7 ms 15968 KB Output is correct
4 Correct 6 ms 15976 KB Output is correct
5 Correct 8 ms 16104 KB Output is correct
6 Correct 7 ms 16068 KB Output is correct
7 Correct 7 ms 16084 KB Output is correct
8 Correct 9 ms 16084 KB Output is correct
9 Correct 67 ms 26484 KB Output is correct
10 Correct 80 ms 28440 KB Output is correct
11 Correct 66 ms 28304 KB Output is correct
12 Correct 69 ms 28864 KB Output is correct
13 Correct 111 ms 28928 KB Output is correct
14 Correct 111 ms 26684 KB Output is correct
15 Correct 629 ms 30084 KB Output is correct
16 Correct 664 ms 29844 KB Output is correct
17 Correct 645 ms 30532 KB Output is correct
18 Correct 1229 ms 30524 KB Output is correct
19 Incorrect 383 ms 20176 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15868 KB Output is correct
3 Incorrect 458 ms 29780 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 7 ms 15868 KB Output is correct
3 Correct 7 ms 15968 KB Output is correct
4 Correct 6 ms 15976 KB Output is correct
5 Correct 8 ms 16104 KB Output is correct
6 Correct 7 ms 16068 KB Output is correct
7 Correct 7 ms 16084 KB Output is correct
8 Correct 9 ms 16084 KB Output is correct
9 Incorrect 7 ms 15956 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 15956 KB Output isn't correct
2 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 15868 KB Output is correct
3 Correct 7 ms 15968 KB Output is correct
4 Correct 6 ms 15976 KB Output is correct
5 Correct 8 ms 16104 KB Output is correct
6 Correct 7 ms 16068 KB Output is correct
7 Correct 7 ms 16084 KB Output is correct
8 Correct 9 ms 16084 KB Output is correct
9 Correct 67 ms 26484 KB Output is correct
10 Correct 80 ms 28440 KB Output is correct
11 Correct 66 ms 28304 KB Output is correct
12 Correct 69 ms 28864 KB Output is correct
13 Correct 111 ms 28928 KB Output is correct
14 Correct 111 ms 26684 KB Output is correct
15 Correct 629 ms 30084 KB Output is correct
16 Correct 664 ms 29844 KB Output is correct
17 Correct 645 ms 30532 KB Output is correct
18 Correct 1229 ms 30524 KB Output is correct
19 Incorrect 458 ms 29780 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -