Submission #405957

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
405957	2021-05-17T05:40:22 Z	tengiz05	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	18572 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;
        }
    }
    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;
    }
    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	15 ms	5060 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	5068 KB	Output is correct
8	Correct	32 ms	5068 KB	Output is correct
9	Execution timed out	2099 ms	18572 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	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	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	15 ms	5060 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	5068 KB	Output is correct
8	Correct	32 ms	5068 KB	Output is correct
9	Correct	4 ms	4940 KB	Output is correct
10	Correct	19 ms	5068 KB	Output is correct
11	Correct	24 ms	5136 KB	Output is correct
12	Correct	24 ms	5068 KB	Output is correct
13	Correct	21 ms	5092 KB	Output is correct
14	Correct	21 ms	5084 KB	Output is correct
15	Incorrect	25 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	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	15 ms	5060 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	5068 KB	Output is correct
9	Correct	32 ms	5068 KB	Output is correct
10	Execution timed out	2099 ms	18572 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	15 ms	5060 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	5068 KB	Output is correct
8	Correct	32 ms	5068 KB	Output is correct
9	Execution timed out	2099 ms	18572 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	15 ms	5060 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	5068 KB	Output is correct
9	Correct	32 ms	5068 KB	Output is correct
10	Execution timed out	2099 ms	18572 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-