oj.uz

Submission #405951

# Submission time Handle Problem Language Result Execution time Memory
405951 2021-05-17T05:33:57 Z tengiz05 Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 18564 KB 
#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 1e5;
std::set<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(V[i]);
            e[V[i]].emplace(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;
    }
    y = Y;
    for (auto x : got) {
        e[x].erase(y);
        e[y].erase(x);
        y = x;
    }
    if (!got.size()) {
        e[X].erase(Y);
        e[Y].erase(X);
    }
    p.assign(n, -1);
    vis.assign(n, false);
    dfs(X, -1);
    if (p[Y] == -1)
        return false;
    return true;
}
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 5 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 13 ms 4940 KB Output is correct
5 Correct 22 ms 5128 KB Output is correct
6 Correct 25 ms 5068 KB Output is correct
7 Correct 28 ms 5068 KB Output is correct
8 Correct 38 ms 5120 KB Output is correct
9 Execution timed out 2082 ms 18564 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Execution timed out 2073 ms 17540 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 13 ms 4940 KB Output is correct
5 Correct 22 ms 5128 KB Output is correct
6 Correct 25 ms 5068 KB Output is correct
7 Correct 28 ms 5068 KB Output is correct
8 Correct 38 ms 5120 KB Output is correct
9 Correct 4 ms 4940 KB Output is correct
10 Correct 25 ms 5096 KB Output is correct
11 Correct 28 ms 5128 KB Output is correct
12 Correct 25 ms 5128 KB Output is correct
13 Correct 22 ms 5092 KB Output is correct
14 Correct 21 ms 5088 KB Output is correct
15 Incorrect 27 ms 5068 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 13 ms 4940 KB Output is correct
6 Correct 22 ms 5128 KB Output is correct
7 Correct 25 ms 5068 KB Output is correct
8 Correct 28 ms 5068 KB Output is correct
9 Correct 38 ms 5120 KB Output is correct
10 Execution timed out 2082 ms 18564 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 13 ms 4940 KB Output is correct
5 Correct 22 ms 5128 KB Output is correct
6 Correct 25 ms 5068 KB Output is correct
7 Correct 28 ms 5068 KB Output is correct
8 Correct 38 ms 5120 KB Output is correct
9 Execution timed out 2082 ms 18564 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 5 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 13 ms 4940 KB Output is correct
6 Correct 22 ms 5128 KB Output is correct
7 Correct 25 ms 5068 KB Output is correct
8 Correct 28 ms 5068 KB Output is correct
9 Correct 38 ms 5120 KB Output is correct
10 Execution timed out 2082 ms 18564 KB Time limit exceeded
11 Halted 0 ms 0 KB -