oj.uz

답안 #405944

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405944 2021-05-17T05:26:00 Z tengiz05 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 13764 KB 
#include "swap.h"
#include <bits/stdc++.h>
constexpr int N = 1e5;
std::vector<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_back(V[i]);
            e[V[i]].emplace_back(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;
    }
    return false;
}
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 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 7 ms 2636 KB Output is correct
6 Correct 8 ms 2636 KB Output is correct
7 Correct 8 ms 2748 KB Output is correct
8 Correct 9 ms 2644 KB Output is correct
9 Correct 470 ms 11296 KB Output is correct
10 Correct 1205 ms 12556 KB Output is correct
11 Correct 1661 ms 13232 KB Output is correct
12 Correct 1786 ms 13412 KB Output is correct
13 Correct 1924 ms 13764 KB Output is correct
14 Execution timed out 2100 ms 11112 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Execution timed out 2082 ms 10792 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 7 ms 2636 KB Output is correct
6 Correct 8 ms 2636 KB Output is correct
7 Correct 8 ms 2748 KB Output is correct
8 Correct 9 ms 2644 KB Output is correct
9 Incorrect 2 ms 2636 KB Output isn't correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 5 ms 2636 KB Output is correct
5 Correct 7 ms 2636 KB Output is correct
6 Correct 8 ms 2636 KB Output is correct
7 Correct 8 ms 2748 KB Output is correct
8 Correct 9 ms 2644 KB Output is correct
9 Correct 470 ms 11296 KB Output is correct
10 Correct 1205 ms 12556 KB Output is correct
11 Correct 1661 ms 13232 KB Output is correct
12 Correct 1786 ms 13412 KB Output is correct
13 Correct 1924 ms 13764 KB Output is correct
14 Execution timed out 2100 ms 11112 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct