oj.uz

답안 #406052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406052 2021-05-17T07:17:50 Z tengiz05 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 18704 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 = -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

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

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

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

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

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

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