Submission #405921

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
405921	2021-05-17T04:43:48 Z	tengiz05	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	18564 KB

swap

#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;
        }
    }
    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	4 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	13 ms	5052 KB	Output is correct
5	Correct	21 ms	5144 KB	Output is correct
6	Correct	25 ms	5128 KB	Output is correct
7	Correct	29 ms	5152 KB	Output is correct
8	Correct	31 ms	5068 KB	Output is correct
9	Execution timed out	2097 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	4 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Execution timed out	2077 ms	17524 KB	Time limit exceeded
4	Halted	0 ms	0 KB	-

Subtask #3

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	13 ms	5052 KB	Output is correct
5	Correct	21 ms	5144 KB	Output is correct
6	Correct	25 ms	5128 KB	Output is correct
7	Correct	29 ms	5152 KB	Output is correct
8	Correct	31 ms	5068 KB	Output is correct
9	Correct	4 ms	4940 KB	Output is correct
10	Correct	20 ms	5108 KB	Output is correct
11	Correct	25 ms	5068 KB	Output is correct
12	Correct	25 ms	5144 KB	Output is correct
13	Correct	21 ms	5104 KB	Output is correct
14	Correct	21 ms	5108 KB	Output is correct
15	Incorrect	25 ms	5196 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	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	13 ms	5052 KB	Output is correct
6	Correct	21 ms	5144 KB	Output is correct
7	Correct	25 ms	5128 KB	Output is correct
8	Correct	29 ms	5152 KB	Output is correct
9	Correct	31 ms	5068 KB	Output is correct
10	Execution timed out	2097 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	4 ms	4940 KB	Output is correct
2	Correct	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	13 ms	5052 KB	Output is correct
5	Correct	21 ms	5144 KB	Output is correct
6	Correct	25 ms	5128 KB	Output is correct
7	Correct	29 ms	5152 KB	Output is correct
8	Correct	31 ms	5068 KB	Output is correct
9	Execution timed out	2097 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	4 ms	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	13 ms	5052 KB	Output is correct
6	Correct	21 ms	5144 KB	Output is correct
7	Correct	25 ms	5128 KB	Output is correct
8	Correct	29 ms	5152 KB	Output is correct
9	Correct	31 ms	5068 KB	Output is correct
10	Execution timed out	2097 ms	18564 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-