oj.uz

답안 #405957

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405957 2021-05-17T05:40:22 Z tengiz05 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 18572 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;
        }
    }
    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

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

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

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

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

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

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