oj.uz

Submission #405944

# Submission time Handle Problem Language Result Execution time Memory
405944 2021-05-17T05:26:00 Z tengiz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 13764 KB 
#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 1e5;
std::vector<int> e[N];
std::vector<int> U, V, W;
int n, m;
void init(int n, int m, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    ::U = U;
    ::V = V;
    ::W = W;
    ::n = n;
    ::m = m;
}
std::vector<int> p;
std::vector<bool> vis;
void dfs(int u, int P) {
    p[u] = P;
    vis[u] = true;
    for (auto v : e[u]) {
        if (!vis[v]) {
            dfs(v, u);
        }
    }
}
bool check(int X, int Y, int mid) {
    for (int i = 0; i < n; i++) e[i].clear();
    for (int i = 0; i < m; i++) {
        if (W[i] <= mid) {
            e[U[i]].emplace_back(V[i]);
            e[V[i]].emplace_back(U[i]);
        }
    }
    p.assign(n, -1);
    vis.assign(n, false);
    dfs(X, -1);
    if (p[Y] == -1)
        return false;
    int y = Y;
    std::vector<int> got;
    y = p[y];
    while (y != -1 && p[y] != -1) {
        got.push_back(y);
        y = p[y];
    }
    for (auto x : got) {
        if (e[x].size() > 2) {
            return true;
        }
    }
    if (e[X].size() > 2 && e[Y].size() > 2) {
        return true;
    }
    return false;
}
int getMinimumFuelCapacity(int X, int Y) {
    int l = 0, r = 1e9 + 1;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(X, Y, mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if (r == 1e9 + 1) r = -1;
    return r;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 7 ms 2636 KB Output is correct
6 Correct 8 ms 2636 KB Output is correct
7 Correct 8 ms 2748 KB Output is correct
8 Correct 9 ms 2644 KB Output is correct
9 Correct 470 ms 11296 KB Output is correct
10 Correct 1205 ms 12556 KB Output is correct
11 Correct 1661 ms 13232 KB Output is correct
12 Correct 1786 ms 13412 KB Output is correct
13 Correct 1924 ms 13764 KB Output is correct
14 Execution timed out 2100 ms 11112 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 7 ms 2636 KB Output is correct
6 Correct 8 ms 2636 KB Output is correct
7 Correct 8 ms 2748 KB Output is correct
8 Correct 9 ms 2644 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 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 7 ms 2636 KB Output is correct
6 Correct 8 ms 2636 KB Output is correct
7 Correct 8 ms 2748 KB Output is correct
8 Correct 9 ms 2644 KB Output is correct
9 Correct 470 ms 11296 KB Output is correct
10 Correct 1205 ms 12556 KB Output is correct
11 Correct 1661 ms 13232 KB Output is correct
12 Correct 1786 ms 13412 KB Output is correct
13 Correct 1924 ms 13764 KB Output is correct
14 Execution timed out 2100 ms 11112 KB Time limit exceeded
15 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