Submission #406052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
406052	2021-05-17T07:17:50 Z	tengiz05	Swapping Cities (APIO20_swap)	C++17	0 / 100	2000 ms	18704 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 = -1, 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	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	13 ms	5056 KB	Output is correct
5	Correct	22 ms	5068 KB	Output is correct
6	Correct	25 ms	5132 KB	Output is correct
7	Correct	29 ms	5152 KB	Output is correct
8	Correct	32 ms	5068 KB	Output is correct
9	Execution timed out	2093 ms	18704 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	4940 KB	Output is correct
3	Execution timed out	2086 ms	17516 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	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	13 ms	5056 KB	Output is correct
5	Correct	22 ms	5068 KB	Output is correct
6	Correct	25 ms	5132 KB	Output is correct
7	Correct	29 ms	5152 KB	Output is correct
8	Correct	32 ms	5068 KB	Output is correct
9	Correct	3 ms	4940 KB	Output is correct
10	Correct	19 ms	5068 KB	Output is correct
11	Correct	25 ms	5136 KB	Output is correct
12	Correct	32 ms	5124 KB	Output is correct
13	Correct	22 ms	5196 KB	Output is correct
14	Correct	21 ms	5088 KB	Output is correct
15	Incorrect	25 ms	5124 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	4940 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	13 ms	5056 KB	Output is correct
6	Correct	22 ms	5068 KB	Output is correct
7	Correct	25 ms	5132 KB	Output is correct
8	Correct	29 ms	5152 KB	Output is correct
9	Correct	32 ms	5068 KB	Output is correct
10	Execution timed out	2093 ms	18704 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	4940 KB	Output is correct
3	Correct	4 ms	4940 KB	Output is correct
4	Correct	13 ms	5056 KB	Output is correct
5	Correct	22 ms	5068 KB	Output is correct
6	Correct	25 ms	5132 KB	Output is correct
7	Correct	29 ms	5152 KB	Output is correct
8	Correct	32 ms	5068 KB	Output is correct
9	Execution timed out	2093 ms	18704 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	4940 KB	Output is correct
4	Correct	4 ms	4940 KB	Output is correct
5	Correct	13 ms	5056 KB	Output is correct
6	Correct	22 ms	5068 KB	Output is correct
7	Correct	25 ms	5132 KB	Output is correct
8	Correct	29 ms	5152 KB	Output is correct
9	Correct	32 ms	5068 KB	Output is correct
10	Execution timed out	2093 ms	18704 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-