oj.uz

Submission #569729

# Submission time Handle Problem Language Result Execution time Memory
569729 2022-05-27T16:40:05 Z ryangohca Swapping Cities (APIO20_swap) C++17
6 / 100
 1022 ms 23608 KB 
#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
int p[100001], pweight[100001][20], st[100001], en[100001], lineWeight[100001], twok[100001][20];
void init(int N){
    iota(p, p+N, 0);
    iota(st, st+N, 0);
    iota(en, en+N, 0);
    fill(lineWeight, lineWeight+N, 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] = min(lineWeight[px], 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] = min(lineWeight[px], w);
        }
    } else {
        st[px] = en[px] = -1;
      	lineWeight[px] = w;//min(lineWeight[px], lineWeight[py]);
    }
}
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]);
            }
        }
    }
}
bool isOkay(int mid, int X, int Y){
    for (int i = 19; i >= 0; i--){
        if (twok[X][i] != -1 && pweight[X][i] <= mid) X = twok[X][i];
        if (twok[Y][i] != -1 && pweight[Y][i] <= mid) Y = twok[Y][i];
    }
    if (X != Y) return false;
    return lineWeight[X] != -1 && lineWeight[X] <= 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 9 ms 15956 KB Output is correct
3 Correct 9 ms 15956 KB Output is correct
4 Correct 9 ms 15956 KB Output is correct
5 Correct 10 ms 15936 KB Output is correct
6 Correct 9 ms 15956 KB Output is correct
7 Correct 9 ms 15940 KB Output is correct
8 Correct 7 ms 16020 KB Output is correct
9 Correct 50 ms 20932 KB Output is correct
10 Correct 59 ms 21584 KB Output is correct
11 Correct 72 ms 21588 KB Output is correct
12 Correct 78 ms 21676 KB Output is correct
13 Correct 82 ms 21724 KB Output is correct
14 Correct 95 ms 21032 KB Output is correct
15 Correct 608 ms 23460 KB Output is correct
16 Correct 593 ms 23436 KB Output is correct
17 Correct 548 ms 23516 KB Output is correct
18 Correct 969 ms 23584 KB Output is correct
19 Correct 317 ms 20400 KB Output is correct
20 Correct 539 ms 23076 KB Output is correct
21 Correct 522 ms 23040 KB Output is correct
22 Correct 533 ms 23364 KB Output is correct
23 Correct 1022 ms 23544 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15956 KB Output is correct
2 Correct 9 ms 15956 KB Output is correct
3 Incorrect 445 ms 23608 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 9 ms 15956 KB Output is correct
3 Correct 9 ms 15956 KB Output is correct
4 Correct 9 ms 15956 KB Output is correct
5 Correct 10 ms 15936 KB Output is correct
6 Correct 9 ms 15956 KB Output is correct
7 Correct 9 ms 15940 KB Output is correct
8 Correct 7 ms 16020 KB Output is correct
9 Incorrect 8 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 8 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 9 ms 15956 KB Output is correct
3 Correct 9 ms 15956 KB Output is correct
4 Correct 9 ms 15956 KB Output is correct
5 Correct 10 ms 15936 KB Output is correct
6 Correct 9 ms 15956 KB Output is correct
7 Correct 9 ms 15940 KB Output is correct
8 Correct 7 ms 16020 KB Output is correct
9 Correct 50 ms 20932 KB Output is correct
10 Correct 59 ms 21584 KB Output is correct
11 Correct 72 ms 21588 KB Output is correct
12 Correct 78 ms 21676 KB Output is correct
13 Correct 82 ms 21724 KB Output is correct
14 Correct 95 ms 21032 KB Output is correct
15 Correct 608 ms 23460 KB Output is correct
16 Correct 593 ms 23436 KB Output is correct
17 Correct 548 ms 23516 KB Output is correct
18 Correct 969 ms 23584 KB Output is correct
19 Incorrect 445 ms 23608 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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