oj.uz

Submission #428985

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

using namespace std;

const int MAX = 1e5+5;
const int INF = 1e9;

int n, m, used[MAX];
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;
    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]});
    }
}

void dfs (int v, int p, int k, int& flag){
    used[v] = 1;
    int deg = 0;
    for (auto i: g[v]) {
        if (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 3 ms 3020 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 4 ms 3020 KB Output is correct
4 Correct 6 ms 3028 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 10 ms 3176 KB Output is correct
7 Correct 8 ms 3148 KB Output is correct
8 Correct 8 ms 3148 KB Output is correct
9 Correct 311 ms 14908 KB Output is correct
10 Correct 881 ms 16324 KB Output is correct
11 Correct 1289 ms 16780 KB Output is correct
12 Correct 1353 ms 16492 KB Output is correct
13 Correct 1758 ms 17484 KB Output is correct
14 Execution timed out 2058 ms 14600 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Execution timed out 2069 ms 12388 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 4 ms 3020 KB Output is correct
4 Correct 6 ms 3028 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 10 ms 3176 KB Output is correct
7 Correct 8 ms 3148 KB Output is correct
8 Correct 8 ms 3148 KB Output is correct
9 Correct 4 ms 3020 KB Output is correct
10 Correct 6 ms 3020 KB Output is correct
11 Correct 8 ms 3156 KB Output is correct
12 Correct 8 ms 3020 KB Output is correct
13 Correct 7 ms 3020 KB Output is correct
14 Correct 6 ms 3020 KB Output is correct
15 Correct 6 ms 3020 KB Output is correct
16 Correct 8 ms 3148 KB Output is correct
17 Correct 7 ms 3176 KB Output is correct
18 Correct 7 ms 3020 KB Output is correct
19 Correct 6 ms 3020 KB Output is correct
20 Correct 7 ms 3148 KB Output is correct
21 Correct 7 ms 3020 KB Output is correct
22 Correct 9 ms 3148 KB Output is correct
23 Correct 6 ms 3020 KB Output is correct
24 Incorrect 6 ms 3216 KB Output isn't correct
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 4 ms 3020 KB Output is correct
5 Correct 6 ms 3028 KB Output is correct
6 Correct 6 ms 3276 KB Output is correct
7 Correct 10 ms 3176 KB Output is correct
8 Correct 8 ms 3148 KB Output is correct
9 Correct 8 ms 3148 KB Output is correct
10 Correct 311 ms 14908 KB Output is correct
11 Correct 881 ms 16324 KB Output is correct
12 Correct 1289 ms 16780 KB Output is correct
13 Correct 1353 ms 16492 KB Output is correct
14 Correct 1758 ms 17484 KB Output is correct
15 Correct 6 ms 3020 KB Output is correct
16 Correct 8 ms 3156 KB Output is correct
17 Correct 8 ms 3020 KB Output is correct
18 Correct 7 ms 3020 KB Output is correct
19 Correct 6 ms 3020 KB Output is correct
20 Correct 6 ms 3020 KB Output is correct
21 Correct 8 ms 3148 KB Output is correct
22 Correct 7 ms 3176 KB Output is correct
23 Correct 7 ms 3020 KB Output is correct
24 Correct 6 ms 3020 KB Output is correct
25 Correct 7 ms 3148 KB Output is correct
26 Correct 7 ms 3020 KB Output is correct
27 Correct 9 ms 3148 KB Output is correct
28 Correct 6 ms 3020 KB Output is correct
29 Incorrect 6 ms 3216 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 4 ms 3020 KB Output is correct
4 Correct 6 ms 3028 KB Output is correct
5 Correct 6 ms 3276 KB Output is correct
6 Correct 10 ms 3176 KB Output is correct
7 Correct 8 ms 3148 KB Output is correct
8 Correct 8 ms 3148 KB Output is correct
9 Correct 311 ms 14908 KB Output is correct
10 Correct 881 ms 16324 KB Output is correct
11 Correct 1289 ms 16780 KB Output is correct
12 Correct 1353 ms 16492 KB Output is correct
13 Correct 1758 ms 17484 KB Output is correct
14 Execution timed out 2058 ms 14600 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3020 KB Output is correct
2 Correct 3 ms 3020 KB Output is correct
3 Correct 3 ms 3020 KB Output is correct
4 Correct 4 ms 3020 KB Output is correct
5 Correct 6 ms 3028 KB Output is correct
6 Correct 6 ms 3276 KB Output is correct
7 Correct 10 ms 3176 KB Output is correct
8 Correct 8 ms 3148 KB Output is correct
9 Correct 8 ms 3148 KB Output is correct
10 Correct 311 ms 14908 KB Output is correct
11 Correct 881 ms 16324 KB Output is correct
12 Correct 1289 ms 16780 KB Output is correct
13 Correct 1353 ms 16492 KB Output is correct
14 Correct 1758 ms 17484 KB Output is correct
15 Execution timed out 2058 ms 14600 KB Time limit exceeded
16 Halted 0 ms 0 KB -