Submission #405965

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
405965	2021-05-17T05:50:22 Z	tengiz05	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	18616 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 + 2;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(X, Y, mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if (r == 1e9 + 2) r = -1;
    return r;
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4976 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	13 ms	5056 KB	Output is correct
5	Correct	21 ms	5144 KB	Output is correct
6	Correct	25 ms	5136 KB	Output is correct
7	Correct	28 ms	5068 KB	Output is correct
8	Correct	30 ms	5144 KB	Output is correct
9	Execution timed out	2064 ms	18616 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #2

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4976 KB	Output is correct
3	Execution timed out	2078 ms	18344 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	4940 KB	Output is correct
2	Correct	3 ms	4976 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	13 ms	5056 KB	Output is correct
5	Correct	21 ms	5144 KB	Output is correct
6	Correct	25 ms	5136 KB	Output is correct
7	Correct	28 ms	5068 KB	Output is correct
8	Correct	30 ms	5144 KB	Output is correct
9	Correct	3 ms	4940 KB	Output is correct
10	Correct	18 ms	5104 KB	Output is correct
11	Correct	24 ms	5136 KB	Output is correct
12	Correct	24 ms	5120 KB	Output is correct
13	Correct	20 ms	5068 KB	Output is correct
14	Correct	22 ms	5068 KB	Output is correct
15	Incorrect	24 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	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4976 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	13 ms	5056 KB	Output is correct
6	Correct	21 ms	5144 KB	Output is correct
7	Correct	25 ms	5136 KB	Output is correct
8	Correct	28 ms	5068 KB	Output is correct
9	Correct	30 ms	5144 KB	Output is correct
10	Execution timed out	2064 ms	18616 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4976 KB	Output is correct
3	Correct	3 ms	4940 KB	Output is correct
4	Correct	13 ms	5056 KB	Output is correct
5	Correct	21 ms	5144 KB	Output is correct
6	Correct	25 ms	5136 KB	Output is correct
7	Correct	28 ms	5068 KB	Output is correct
8	Correct	30 ms	5144 KB	Output is correct
9	Execution timed out	2064 ms	18616 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-

Subtask #6

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4940 KB	Output is correct
2	Correct	3 ms	4940 KB	Output is correct
3	Correct	3 ms	4976 KB	Output is correct
4	Correct	3 ms	4940 KB	Output is correct
5	Correct	13 ms	5056 KB	Output is correct
6	Correct	21 ms	5144 KB	Output is correct
7	Correct	25 ms	5136 KB	Output is correct
8	Correct	28 ms	5068 KB	Output is correct
9	Correct	30 ms	5144 KB	Output is correct
10	Execution timed out	2064 ms	18616 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-