oj.uz

답안 #793354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793354 2023-07-25T18:15:56 Z Valaki2 007 (CEOI14_007) C++14
0 / 100
 163 ms 17796 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int maxn = 2e5;

int n, m;
vector<int> graph[1 + maxn];
int g, s, a, b;
vector<int> dg, ds, da, db;

vector<int> bfs(int start) {
    vector<int> res(1 + n, -1);
    res[start] = 0;
    queue<int> q;
    q.push(start);
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int nei : graph[cur]) {
            if(res[nei] == -1) {
                res[nei] = res[cur] + 1;
                q.push(nei);
            }
        }
    }
    return res;
}

void solve() {
    cin >> n >> m;
    cin >> g >> s >> a >> b;
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].pb(y);
        graph[y].pb(x);
    }
    dg = bfs(g), ds = bfs(s), da = bfs(a), db = bfs(b);
    if((da[s] < da[g]) || (db[s] < db[g])) {
        cout << "-1\n";
        return;
    }
    int add_a = da[s] - 1 - da[g], add_b = db[s] - 1 - db[g];
    bool extra_case = true;
    if(add_a != add_b) {
        add_a++, add_b++;
        extra_case = false;
    }
    int to_add = min(add_a, add_b);
    if(!extra_case) {
        cout << to_add << "\n";
        return;
    }
    to_add++;
    da[s] += to_add;
    db[s] += to_add;
    int closest_g = n + 1, closest_s = n + 1;
    if(da[s] != db[s] || da[g] != db[g]) {
        exit(1);
    }
    for(int cur = 1; cur <= n; cur++) {
        int dab = max(da[cur], db[cur]);
        if(dab + closest_g == da[g]) {
            closest_g = min(closest_g, dab);
        }
        if(dab + closest_s == db[s]) {
            closest_s = min(closest_s, dab);
        }
    }
    if(closest_s < closest_g) {
        to_add--;
    }
    cout << to_add << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 2 ms 4948 KB Execution failed because the return code was nonzero
3 Correct 3 ms 4948 KB Output is correct
4 Incorrect 2 ms 4948 KB Output isn't correct
5 Incorrect 2 ms 5020 KB Output isn't correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 4948 KB Output is correct
8 Incorrect 2 ms 4948 KB Output isn't correct
9 Correct 2 ms 5024 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Incorrect 2 ms 5020 KB Output isn't correct
13 Correct 2 ms 4948 KB Output is correct
14 Incorrect 2 ms 4948 KB Output isn't correct
15 Correct 2 ms 5020 KB Output is correct
16 Incorrect 2 ms 4948 KB Output isn't correct
17 Incorrect 2 ms 4948 KB Output isn't correct
18 Incorrect 2 ms 5024 KB Output isn't correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 5024 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Correct 3 ms 4948 KB Output is correct
23 Correct 3 ms 4960 KB Output is correct
24 Incorrect 3 ms 5028 KB Output isn't correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 7180 KB Output is correct
2 Incorrect 17 ms 8172 KB Output isn't correct
3 Correct 16 ms 7196 KB Output is correct
4 Incorrect 19 ms 8216 KB Output isn't correct
5 Correct 15 ms 7028 KB Output is correct
6 Correct 14 ms 7316 KB Output is correct
7 Correct 17 ms 7580 KB Output is correct
8 Correct 18 ms 7524 KB Output is correct
9 Incorrect 26 ms 8012 KB Output isn't correct
10 Correct 96 ms 12460 KB Output is correct
11 Incorrect 30 ms 9664 KB Output isn't correct
12 Correct 51 ms 10636 KB Output is correct
13 Incorrect 35 ms 9924 KB Output isn't correct
14 Correct 25 ms 9208 KB Output is correct
15 Correct 35 ms 10864 KB Output is correct
16 Correct 38 ms 11128 KB Output is correct
17 Correct 32 ms 10444 KB Output is correct
18 Incorrect 35 ms 10468 KB Output isn't correct
19 Correct 59 ms 11668 KB Output is correct
20 Incorrect 116 ms 14528 KB Output isn't correct
21 Incorrect 52 ms 12876 KB Output isn't correct
22 Correct 44 ms 11920 KB Output is correct
23 Runtime error 46 ms 12724 KB Execution failed because the return code was nonzero
24 Correct 51 ms 12728 KB Output is correct
25 Incorrect 47 ms 12300 KB Output isn't correct
26 Runtime error 44 ms 11924 KB Execution failed because the return code was nonzero
27 Correct 51 ms 12844 KB Output is correct
28 Correct 81 ms 12848 KB Output is correct
29 Correct 82 ms 13336 KB Output is correct
30 Incorrect 136 ms 15348 KB Output isn't correct
31 Incorrect 59 ms 13952 KB Output isn't correct
32 Correct 53 ms 12772 KB Output is correct
33 Runtime error 57 ms 13104 KB Execution failed because the return code was nonzero
34 Incorrect 66 ms 13440 KB Output isn't correct
35 Incorrect 60 ms 13160 KB Output isn't correct
36 Incorrect 60 ms 13460 KB Output isn't correct
37 Correct 62 ms 14300 KB Output is correct
38 Correct 67 ms 14108 KB Output is correct
39 Correct 84 ms 14152 KB Output is correct
40 Incorrect 138 ms 15696 KB Output isn't correct
41 Correct 163 ms 17796 KB Output is correct