oj.uz

Submission #874611

# Submission time Handle Problem Language Result Execution time Memory
874611 2023-11-17T11:39:03 Z SUNWOOOOOOOO Swapping Cities (APIO20_swap) C++17
6 / 100
 353 ms 42692 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 4 ms 18876 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19036 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 100 ms 35328 KB Output is correct
10 Correct 151 ms 38628 KB Output is correct
11 Correct 128 ms 38240 KB Output is correct
12 Correct 135 ms 39248 KB Output is correct
13 Correct 97 ms 31684 KB Output is correct
14 Correct 104 ms 35412 KB Output is correct
15 Correct 353 ms 40784 KB Output is correct
16 Correct 280 ms 40056 KB Output is correct
17 Correct 312 ms 41528 KB Output is correct
18 Correct 168 ms 33360 KB Output is correct
19 Correct 97 ms 25584 KB Output is correct
20 Correct 320 ms 41996 KB Output is correct
21 Correct 277 ms 41348 KB Output is correct
22 Correct 336 ms 42692 KB Output is correct
23 Correct 171 ms 34864 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 4 ms 18876 KB Output is correct
3 Incorrect 151 ms 33448 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 4 ms 18876 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19036 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 4 ms 19032 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 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 18876 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19032 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 4 ms 19036 KB Output is correct
10 Correct 100 ms 35328 KB Output is correct
11 Correct 151 ms 38628 KB Output is correct
12 Correct 128 ms 38240 KB Output is correct
13 Correct 135 ms 39248 KB Output is correct
14 Correct 97 ms 31684 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 4 ms 18876 KB Output is correct
3 Correct 4 ms 19036 KB Output is correct
4 Correct 4 ms 19032 KB Output is correct
5 Correct 4 ms 19036 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 100 ms 35328 KB Output is correct
10 Correct 151 ms 38628 KB Output is correct
11 Correct 128 ms 38240 KB Output is correct
12 Correct 135 ms 39248 KB Output is correct
13 Correct 97 ms 31684 KB Output is correct
14 Correct 104 ms 35412 KB Output is correct
15 Correct 353 ms 40784 KB Output is correct
16 Correct 280 ms 40056 KB Output is correct
17 Correct 312 ms 41528 KB Output is correct
18 Correct 168 ms 33360 KB Output is correct
19 Incorrect 151 ms 33448 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19032 KB Output is correct
2 Correct 4 ms 19036 KB Output is correct
3 Correct 4 ms 18876 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19032 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 4 ms 19036 KB Output is correct
10 Correct 100 ms 35328 KB Output is correct
11 Correct 151 ms 38628 KB Output is correct
12 Correct 128 ms 38240 KB Output is correct
13 Correct 135 ms 39248 KB Output is correct
14 Correct 97 ms 31684 KB Output is correct
15 Correct 104 ms 35412 KB Output is correct
16 Correct 353 ms 40784 KB Output is correct
17 Correct 280 ms 40056 KB Output is correct
18 Correct 312 ms 41528 KB Output is correct
19 Correct 168 ms 33360 KB Output is correct
20 Incorrect 151 ms 33448 KB Output isn't correct
21 Halted 0 ms 0 KB -