oj.uz

Submission #874606

# Submission time Handle Problem Language Result Execution time Memory
874606 2023-11-17T11:29:16 Z SUNWOOOOOOOO Swapping Cities (APIO20_swap) C++17
6 / 100
 329 ms 47280 KB 
// #include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using tint = array <int, 3>;
const int mxN = 200005;
vector <int> info1[mxN], info2[mxN]; // time, group
int n, m, deg[mxN], ftime[mxN]; // time when deg3 or cycle
tint edge[mxN];

struct dsu {
    int G[mxN];
    vector <int> Gelm[mxN];
    void init(){
        for (int i = 0; i < n; i++){
            G[i] = i;
            Gelm[i].push_back(i);
            info1[i].push_back(-1);
            info2[i].push_back(i);
        }
    }
    void uni(int time, int x, int y){
        x = G[x], y = G[y];
        if (x != y){
            if (Gelm[x].size() < Gelm[y].size()) swap(x, y);
            for (int elm : Gelm[y]) {
                G[elm] = x;
                Gelm[x].push_back(elm);
                info1[elm].push_back(time);
                info2[elm].push_back(x);
            }
            if (ftime[x] == -1 && ftime[y] != -1) ftime[x] = time;
            Gelm[y].clear();
        }
        if (x == y && ftime[x] == -1) ftime[x] = time;
    }
} dsu;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N, m = M;
    for (int i = 0; i < n; i++) ftime[i] = -1;
    for (int i = 0; i < m; i++) edge[i] = {W[i], U[i], V[i]};
    sort(edge, edge + m);

    dsu.init();
    for (int i = 0; i < m; i++){
        for (int j : {1, 2}){
            int x = edge[i][j];
            if (++deg[x] == 3){
                x = dsu.G[x];
                if (ftime[x] == -1) ftime[x] = i;
            }
        }
        dsu.uni(i, edge[i][1], edge[i][2]);
    }
}

int getMinimumFuelCapacity(int x, int y) {
    int low = 0, high = m - 1, ans = -1;
    while (low <= high){
        int mid = (low + high) / 2;
        int xi = upper_bound(info1[x].begin(), info1[x].end(), mid) - info1[x].begin() - 1;
        int yi = upper_bound(info1[y].begin(), info1[y].end(), mid) - info1[y].begin() - 1;
        x = info2[x][xi], y = info2[y][yi];
        if (x == y && ftime[x] != -1 && ftime[x] <= mid){
            ans = mid;
            high = mid - 1;
        }
        else low = mid + 1;
    }
    return (ans != -1 ? edge[ans][0] : -1);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18884 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19096 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 127 ms 36964 KB Output is correct
10 Correct 163 ms 40492 KB Output is correct
11 Correct 123 ms 40012 KB Output is correct
12 Correct 133 ms 41552 KB Output is correct
13 Correct 96 ms 33824 KB Output is correct
14 Correct 102 ms 37204 KB Output is correct
15 Correct 273 ms 45160 KB Output is correct
16 Correct 319 ms 44420 KB Output is correct
17 Correct 295 ms 46024 KB Output is correct
18 Correct 171 ms 37808 KB Output is correct
19 Correct 102 ms 27560 KB Output is correct
20 Correct 275 ms 46036 KB Output is correct
21 Correct 329 ms 45644 KB Output is correct
22 Correct 288 ms 47280 KB Output is correct
23 Correct 213 ms 39144 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Incorrect 167 ms 37232 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18884 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19096 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 3 ms 19036 KB Output is correct
10 Incorrect 4 ms 19036 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 18884 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19096 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 127 ms 36964 KB Output is correct
11 Correct 163 ms 40492 KB Output is correct
12 Correct 123 ms 40012 KB Output is correct
13 Correct 133 ms 41552 KB Output is correct
14 Correct 96 ms 33824 KB Output is correct
15 Incorrect 4 ms 19036 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 3 ms 19036 KB Output is correct
3 Correct 3 ms 18884 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19096 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 127 ms 36964 KB Output is correct
10 Correct 163 ms 40492 KB Output is correct
11 Correct 123 ms 40012 KB Output is correct
12 Correct 133 ms 41552 KB Output is correct
13 Correct 96 ms 33824 KB Output is correct
14 Correct 102 ms 37204 KB Output is correct
15 Correct 273 ms 45160 KB Output is correct
16 Correct 319 ms 44420 KB Output is correct
17 Correct 295 ms 46024 KB Output is correct
18 Correct 171 ms 37808 KB Output is correct
19 Incorrect 167 ms 37232 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 19036 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 3 ms 19036 KB Output is correct
4 Correct 3 ms 18884 KB Output is correct
5 Correct 4 ms 19036 KB Output is correct
6 Correct 4 ms 19096 KB Output is correct
7 Correct 4 ms 19036 KB Output is correct
8 Correct 4 ms 19036 KB Output is correct
9 Correct 4 ms 19036 KB Output is correct
10 Correct 127 ms 36964 KB Output is correct
11 Correct 163 ms 40492 KB Output is correct
12 Correct 123 ms 40012 KB Output is correct
13 Correct 133 ms 41552 KB Output is correct
14 Correct 96 ms 33824 KB Output is correct
15 Correct 102 ms 37204 KB Output is correct
16 Correct 273 ms 45160 KB Output is correct
17 Correct 319 ms 44420 KB Output is correct
18 Correct 295 ms 46024 KB Output is correct
19 Correct 171 ms 37808 KB Output is correct
20 Incorrect 167 ms 37232 KB Output isn't correct
21 Halted 0 ms 0 KB -