oj.uz

답안 #793337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793337 2023-07-25T18:00:36 Z Valaki2 007 (CEOI14_007) C++14
30 / 100
 162 ms 17620 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;
    }
    cout << to_add << "\n";
}

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

Subtask #1
9.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Partially correct 2 ms 4948 KB Partially correct
3 Partially correct 2 ms 4948 KB Partially correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Partially correct 2 ms 4948 KB Partially correct
7 Partially correct 2 ms 4948 KB Partially correct
8 Correct 2 ms 4948 KB Output is correct
9 Partially correct 2 ms 4948 KB Partially correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 2 ms 4948 KB Output is correct
13 Partially correct 2 ms 4948 KB Partially correct
14 Correct 2 ms 4948 KB Output is correct
15 Partially correct 2 ms 4948 KB Partially correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Partially correct 2 ms 4948 KB Partially correct
20 Partially correct 2 ms 4948 KB Partially correct
21 Correct 2 ms 4948 KB Output is correct
22 Partially correct 2 ms 4948 KB Partially correct
23 Partially correct 2 ms 4948 KB Partially correct
24 Correct 2 ms 4948 KB Output is correct

Subtask #2
21.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 13 ms 6868 KB Partially correct
2 Correct 17 ms 7716 KB Output is correct
3 Partially correct 15 ms 6996 KB Partially correct
4 Correct 19 ms 7812 KB Output is correct
5 Correct 14 ms 6836 KB Output is correct
6 Correct 13 ms 7124 KB Output is correct
7 Partially correct 16 ms 7344 KB Partially correct
8 Partially correct 16 ms 7252 KB Partially correct
9 Correct 28 ms 7748 KB Output is correct
10 Partially correct 89 ms 12092 KB Partially correct
11 Correct 28 ms 9168 KB Output is correct
12 Partially correct 39 ms 10308 KB Partially correct
13 Correct 32 ms 9584 KB Output is correct
14 Correct 26 ms 8888 KB Output is correct
15 Partially correct 34 ms 10428 KB Partially correct
16 Correct 38 ms 10752 KB Output is correct
17 Partially correct 31 ms 10108 KB Partially correct
18 Correct 34 ms 10072 KB Output is correct
19 Partially correct 58 ms 11340 KB Partially correct
20 Correct 119 ms 14192 KB Output is correct
21 Correct 46 ms 12532 KB Output is correct
22 Partially correct 43 ms 11532 KB Partially correct
23 Partially correct 46 ms 12360 KB Partially correct
24 Partially correct 44 ms 12356 KB Partially correct
25 Correct 51 ms 11912 KB Output is correct
26 Partially correct 42 ms 11608 KB Partially correct
27 Partially correct 50 ms 12452 KB Partially correct
28 Partially correct 54 ms 12464 KB Partially correct
29 Partially correct 87 ms 13052 KB Partially correct
30 Correct 132 ms 14972 KB Output is correct
31 Correct 54 ms 13580 KB Output is correct
32 Partially correct 56 ms 12364 KB Partially correct
33 Partially correct 53 ms 12684 KB Partially correct
34 Correct 58 ms 13068 KB Output is correct
35 Correct 62 ms 12716 KB Output is correct
36 Correct 51 ms 13024 KB Output is correct
37 Correct 69 ms 14160 KB Output is correct
38 Partially correct 60 ms 13952 KB Partially correct
39 Partially correct 75 ms 13900 KB Partially correct
40 Correct 111 ms 15488 KB Output is correct
41 Partially correct 162 ms 17620 KB Partially correct