oj.uz

답안 #405965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405965 2021-05-17T05:50:22 Z tengiz05 자매 도시 (APIO20_swap) C++17
0 / 100
 2000 ms 18616 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 + 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 4976 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 13 ms 5056 KB Output is correct
5 Correct 21 ms 5144 KB Output is correct
6 Correct 25 ms 5136 KB Output is correct
7 Correct 28 ms 5068 KB Output is correct
8 Correct 30 ms 5144 KB Output is correct
9 Execution timed out 2064 ms 18616 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 4976 KB Output is correct
3 Execution timed out 2078 ms 18344 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 4976 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 13 ms 5056 KB Output is correct
5 Correct 21 ms 5144 KB Output is correct
6 Correct 25 ms 5136 KB Output is correct
7 Correct 28 ms 5068 KB Output is correct
8 Correct 30 ms 5144 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 18 ms 5104 KB Output is correct
11 Correct 24 ms 5136 KB Output is correct
12 Correct 24 ms 5120 KB Output is correct
13 Correct 20 ms 5068 KB Output is correct
14 Correct 22 ms 5068 KB Output is correct
15 Incorrect 24 ms 5068 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 4976 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 13 ms 5056 KB Output is correct
6 Correct 21 ms 5144 KB Output is correct
7 Correct 25 ms 5136 KB Output is correct
8 Correct 28 ms 5068 KB Output is correct
9 Correct 30 ms 5144 KB Output is correct
10 Execution timed out 2064 ms 18616 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 4976 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 13 ms 5056 KB Output is correct
5 Correct 21 ms 5144 KB Output is correct
6 Correct 25 ms 5136 KB Output is correct
7 Correct 28 ms 5068 KB Output is correct
8 Correct 30 ms 5144 KB Output is correct
9 Execution timed out 2064 ms 18616 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 4976 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 13 ms 5056 KB Output is correct
6 Correct 21 ms 5144 KB Output is correct
7 Correct 25 ms 5136 KB Output is correct
8 Correct 28 ms 5068 KB Output is correct
9 Correct 30 ms 5144 KB Output is correct
10 Execution timed out 2064 ms 18616 KB Time limit exceeded
11 Halted 0 ms 0 KB -