oj.uz

Submission #428994

# Submission time Handle Problem Language Result Execution time Memory
428994 2021-06-15T16:17:20 Z proma Swapping Cities (APIO20_swap) C++17
0 / 100
 119 ms 14280 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e5+5;

int n, m, used[MAX], inf;
vector <pair <int, int>> g[MAX];

void init (int N, int M, vector <int> U, vector <int> V, vector <int> W) {
    n = N;
    m = M;
    int inf = 0;
    for (int i = 0; i < M; i ++) {
        g[U[i]].push_back({V[i], W[i]});
        g[V[i]].push_back({U[i], W[i]});
        inf = max(inf, W[i]);
    }
}

void dfs (int v, int p, int k, int& flag){
    used[v] = 1;
    int deg = 0;
    for (auto i: g[v]) {
        if (i.second <= k and i.first != p and used[i.first] == 1)
            flag = 1;
        if (i.second <= k and !used[i.first])
            dfs(i.first, v, k, flag);
        if (i.second <= k)
            deg ++;
    }
    if (deg >= 3) flag = 1;
    used[v] = 2;
}

bool isPossible (int a, int b, int k) {
    memset(used, 0, sizeof(used));
    int flag = 0;
    dfs(a, -1, k, flag);
    if (flag and used[b]) return true;
    else return false;
}

int getMinimumFuelCapacity (int X, int Y) {
    int l = 1, r = inf, best = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (isPossible(X, Y, mid)) {
            best = mid;
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return best;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 42 ms 7364 KB Output is correct
10 Correct 61 ms 8324 KB Output is correct
11 Correct 54 ms 8320 KB Output is correct
12 Correct 56 ms 8560 KB Output is correct
13 Correct 57 ms 8668 KB Output is correct
14 Correct 50 ms 8900 KB Output is correct
15 Correct 117 ms 13960 KB Output is correct
16 Correct 116 ms 13904 KB Output is correct
17 Correct 118 ms 14280 KB Output is correct
18 Correct 119 ms 14244 KB Output is correct
19 Incorrect 61 ms 7748 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Incorrect 107 ms 10712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Incorrect 2 ms 2636 KB Output isn't correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 3 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2636 KB Output is correct
8 Correct 3 ms 2636 KB Output is correct
9 Correct 42 ms 7364 KB Output is correct
10 Correct 61 ms 8324 KB Output is correct
11 Correct 54 ms 8320 KB Output is correct
12 Correct 56 ms 8560 KB Output is correct
13 Correct 57 ms 8668 KB Output is correct
14 Correct 50 ms 8900 KB Output is correct
15 Correct 117 ms 13960 KB Output is correct
16 Correct 116 ms 13904 KB Output is correct
17 Correct 118 ms 14280 KB Output is correct
18 Correct 119 ms 14244 KB Output is correct
19 Incorrect 107 ms 10712 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct