oj.uz

답안 #405921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405921 2021-05-17T04:43:48 Z tengiz05 자매 도시 (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;
        }
    }
    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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -