oj.uz

답안 #569865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
569865 2022-05-28T02:07:14 Z ryangohca 자매 도시 (APIO20_swap) C++17
13 / 100
 518 ms 36984 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];
vector<int> linNodes[100001];
void init(int N){
    iota(p, p+N, 0);
    iota(st, st+N, 0);
    iota(en, en+N, 0);
    fill(lineWeight, lineWeight+N, 2e9);
    for (int i = 0; i < N; i++) linNodes[i].push_back(i);
    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 && lineWeight[px] == 2e9){
        st[px] = en[px] = -1;
        for (auto i : linNodes[px]){
            lineWeight[i] = min(lineWeight[i], w);
        }
        return;
    }
    if (linNodes[px].size() < linNodes[py].size()) {swap(x, y); swap(px, py);}
    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]);
            for (auto i : linNodes[py]){
                linNodes[px].push_back(i);
            }
        } else {
            st[px] = en[px] = -1;
            for (auto i : linNodes[px]){
                lineWeight[i] = min(lineWeight[i], w);
            }
            for (auto i : linNodes[py]){
                lineWeight[i] = min(lineWeight[i], w);
            }
        }
    } else if (st[px] != -1){
        st[px] = en[px] = -1;
      	for (auto i : linNodes[px]){
      	    lineWeight[i] = w;
      	}
    } else if (st[py] != -1){
        st[py] = en[py] = -1;
        for (auto i : linNodes[py]){
            lineWeight[i] = w;
        }
    } else {
        lineWeight[px] = 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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 18260 KB Output is correct
2 Correct 8 ms 18244 KB Output is correct
3 Correct 8 ms 18320 KB Output is correct
4 Correct 8 ms 18328 KB Output is correct
5 Correct 8 ms 18388 KB Output is correct
6 Correct 9 ms 18560 KB Output is correct
7 Correct 10 ms 18416 KB Output is correct
8 Correct 9 ms 18388 KB Output is correct
9 Correct 70 ms 29784 KB Output is correct
10 Correct 87 ms 31800 KB Output is correct
11 Correct 88 ms 31692 KB Output is correct
12 Correct 87 ms 32488 KB Output is correct
13 Correct 70 ms 29876 KB Output is correct
14 Correct 119 ms 29960 KB Output is correct
15 Correct 491 ms 36156 KB Output is correct
16 Correct 486 ms 35608 KB Output is correct
17 Correct 496 ms 36536 KB Output is correct
18 Correct 435 ms 33508 KB Output is correct
19 Correct 317 ms 25456 KB Output is correct
20 Correct 462 ms 36172 KB Output is correct
21 Correct 518 ms 35996 KB Output is correct
22 Correct 516 ms 36984 KB Output is correct
23 Correct 442 ms 34064 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 18260 KB Output is correct
2 Correct 8 ms 18244 KB Output is correct
3 Correct 437 ms 28036 KB Output is correct
4 Correct 422 ms 28432 KB Output is correct
5 Correct 452 ms 28296 KB Output is correct
6 Correct 425 ms 28416 KB Output is correct
7 Correct 442 ms 28356 KB Output is correct
8 Correct 437 ms 28104 KB Output is correct
9 Correct 439 ms 28260 KB Output is correct
10 Correct 444 ms 27996 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 18260 KB Output is correct
2 Correct 8 ms 18244 KB Output is correct
3 Correct 8 ms 18320 KB Output is correct
4 Correct 8 ms 18328 KB Output is correct
5 Correct 8 ms 18388 KB Output is correct
6 Correct 9 ms 18560 KB Output is correct
7 Correct 10 ms 18416 KB Output is correct
8 Correct 9 ms 18388 KB Output is correct
9 Correct 8 ms 18260 KB Output is correct
10 Correct 10 ms 18388 KB Output is correct
11 Correct 10 ms 18328 KB Output is correct
12 Correct 9 ms 18388 KB Output is correct
13 Correct 10 ms 18296 KB Output is correct
14 Correct 9 ms 18388 KB Output is correct
15 Correct 9 ms 18396 KB Output is correct
16 Correct 9 ms 18388 KB Output is correct
17 Correct 9 ms 18388 KB Output is correct
18 Correct 9 ms 18388 KB Output is correct
19 Correct 9 ms 18388 KB Output is correct
20 Correct 10 ms 18516 KB Output is correct
21 Correct 10 ms 18404 KB Output is correct
22 Correct 9 ms 18376 KB Output is correct
23 Correct 9 ms 18388 KB Output is correct
24 Incorrect 9 ms 18416 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 18260 KB Output is correct
2 Correct 8 ms 18260 KB Output is correct
3 Correct 8 ms 18244 KB Output is correct
4 Correct 8 ms 18320 KB Output is correct
5 Correct 8 ms 18328 KB Output is correct
6 Correct 8 ms 18388 KB Output is correct
7 Correct 9 ms 18560 KB Output is correct
8 Correct 10 ms 18416 KB Output is correct
9 Correct 9 ms 18388 KB Output is correct
10 Correct 70 ms 29784 KB Output is correct
11 Correct 87 ms 31800 KB Output is correct
12 Correct 88 ms 31692 KB Output is correct
13 Correct 87 ms 32488 KB Output is correct
14 Correct 70 ms 29876 KB Output is correct
15 Correct 10 ms 18388 KB Output is correct
16 Correct 10 ms 18328 KB Output is correct
17 Correct 9 ms 18388 KB Output is correct
18 Correct 10 ms 18296 KB Output is correct
19 Correct 9 ms 18388 KB Output is correct
20 Correct 9 ms 18396 KB Output is correct
21 Correct 9 ms 18388 KB Output is correct
22 Correct 9 ms 18388 KB Output is correct
23 Correct 9 ms 18388 KB Output is correct
24 Correct 9 ms 18388 KB Output is correct
25 Correct 10 ms 18516 KB Output is correct
26 Correct 10 ms 18404 KB Output is correct
27 Correct 9 ms 18376 KB Output is correct
28 Correct 9 ms 18388 KB Output is correct
29 Incorrect 9 ms 18416 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 18260 KB Output is correct
2 Correct 8 ms 18244 KB Output is correct
3 Correct 8 ms 18320 KB Output is correct
4 Correct 8 ms 18328 KB Output is correct
5 Correct 8 ms 18388 KB Output is correct
6 Correct 9 ms 18560 KB Output is correct
7 Correct 10 ms 18416 KB Output is correct
8 Correct 9 ms 18388 KB Output is correct
9 Correct 70 ms 29784 KB Output is correct
10 Correct 87 ms 31800 KB Output is correct
11 Correct 88 ms 31692 KB Output is correct
12 Correct 87 ms 32488 KB Output is correct
13 Correct 70 ms 29876 KB Output is correct
14 Correct 119 ms 29960 KB Output is correct
15 Correct 491 ms 36156 KB Output is correct
16 Correct 486 ms 35608 KB Output is correct
17 Correct 496 ms 36536 KB Output is correct
18 Correct 435 ms 33508 KB Output is correct
19 Correct 437 ms 28036 KB Output is correct
20 Correct 422 ms 28432 KB Output is correct
21 Correct 452 ms 28296 KB Output is correct
22 Correct 425 ms 28416 KB Output is correct
23 Correct 442 ms 28356 KB Output is correct
24 Correct 437 ms 28104 KB Output is correct
25 Correct 439 ms 28260 KB Output is correct
26 Correct 444 ms 27996 KB Output is correct
27 Correct 10 ms 18388 KB Output is correct
28 Correct 10 ms 18328 KB Output is correct
29 Correct 9 ms 18388 KB Output is correct
30 Correct 10 ms 18296 KB Output is correct
31 Correct 9 ms 18388 KB Output is correct
32 Correct 9 ms 18396 KB Output is correct
33 Correct 9 ms 18388 KB Output is correct
34 Correct 9 ms 18388 KB Output is correct
35 Correct 9 ms 18388 KB Output is correct
36 Correct 16 ms 19796 KB Output is correct
37 Correct 95 ms 31160 KB Output is correct
38 Correct 99 ms 30800 KB Output is correct
39 Correct 83 ms 30036 KB Output is correct
40 Correct 81 ms 29276 KB Output is correct
41 Correct 80 ms 28676 KB Output is correct
42 Correct 73 ms 27876 KB Output is correct
43 Incorrect 88 ms 32100 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 18260 KB Output is correct
2 Correct 8 ms 18260 KB Output is correct
3 Correct 8 ms 18244 KB Output is correct
4 Correct 8 ms 18320 KB Output is correct
5 Correct 8 ms 18328 KB Output is correct
6 Correct 8 ms 18388 KB Output is correct
7 Correct 9 ms 18560 KB Output is correct
8 Correct 10 ms 18416 KB Output is correct
9 Correct 9 ms 18388 KB Output is correct
10 Correct 70 ms 29784 KB Output is correct
11 Correct 87 ms 31800 KB Output is correct
12 Correct 88 ms 31692 KB Output is correct
13 Correct 87 ms 32488 KB Output is correct
14 Correct 70 ms 29876 KB Output is correct
15 Correct 119 ms 29960 KB Output is correct
16 Correct 491 ms 36156 KB Output is correct
17 Correct 486 ms 35608 KB Output is correct
18 Correct 496 ms 36536 KB Output is correct
19 Correct 435 ms 33508 KB Output is correct
20 Correct 437 ms 28036 KB Output is correct
21 Correct 422 ms 28432 KB Output is correct
22 Correct 452 ms 28296 KB Output is correct
23 Correct 425 ms 28416 KB Output is correct
24 Correct 442 ms 28356 KB Output is correct
25 Correct 437 ms 28104 KB Output is correct
26 Correct 439 ms 28260 KB Output is correct
27 Correct 444 ms 27996 KB Output is correct
28 Correct 10 ms 18388 KB Output is correct
29 Correct 10 ms 18328 KB Output is correct
30 Correct 9 ms 18388 KB Output is correct
31 Correct 10 ms 18296 KB Output is correct
32 Correct 9 ms 18388 KB Output is correct
33 Correct 9 ms 18396 KB Output is correct
34 Correct 9 ms 18388 KB Output is correct
35 Correct 9 ms 18388 KB Output is correct
36 Correct 9 ms 18388 KB Output is correct
37 Correct 16 ms 19796 KB Output is correct
38 Correct 95 ms 31160 KB Output is correct
39 Correct 99 ms 30800 KB Output is correct
40 Correct 83 ms 30036 KB Output is correct
41 Correct 81 ms 29276 KB Output is correct
42 Correct 80 ms 28676 KB Output is correct
43 Correct 73 ms 27876 KB Output is correct
44 Incorrect 88 ms 32100 KB Output isn't correct
45 Halted 0 ms 0 KB -