oj.uz

답안 #793330

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793330 2023-07-25T17:56:15 Z Valaki2 007 (CEOI14_007) C++14
23 / 100
 176 ms 25012 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";
    }
    int add_a = da[s] - 1 - da[g], add_b = db[s] - 1 - db[g];
    if(add_a != add_b) {
        add_a++, add_b++;
    }
    int to_add = min(add_a, add_b);
    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 4948 KB Output is correct
5 Correct 2 ms 5020 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 5020 KB Output is correct
12 Correct 3 ms 5024 KB Output is correct
13 Partially correct 2 ms 5028 KB Partially correct
14 Correct 3 ms 4992 KB Output is correct
15 Partially correct 2 ms 4948 KB Partially correct
16 Correct 3 ms 5032 KB Output is correct
17 Correct 3 ms 4944 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 5028 KB Output is correct
22 Partially correct 2 ms 4948 KB Partially correct
23 Partially correct 2 ms 4948 KB Partially correct
24 Correct 3 ms 5020 KB Output is correct

Subtask #2
14.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 16 ms 7420 KB Partially correct
2 Correct 22 ms 8436 KB Output is correct
3 Partially correct 15 ms 7520 KB Partially correct
4 Correct 22 ms 8528 KB Output is correct
5 Correct 15 ms 7304 KB Output is correct
6 Correct 14 ms 7564 KB Output is correct
7 Partially correct 15 ms 7892 KB Partially correct
8 Partially correct 16 ms 7872 KB Partially correct
9 Correct 24 ms 8748 KB Output is correct
10 Partially correct 107 ms 17284 KB Partially correct
11 Correct 37 ms 10324 KB Output is correct
12 Partially correct 40 ms 11704 KB Partially correct
13 Correct 37 ms 10724 KB Output is correct
14 Incorrect 26 ms 9816 KB Extra information in the output file
15 Partially correct 36 ms 11740 KB Partially correct
16 Correct 36 ms 12132 KB Output is correct
17 Partially correct 33 ms 11360 KB Partially correct
18 Correct 36 ms 11436 KB Output is correct
19 Partially correct 58 ms 13852 KB Partially correct
20 Correct 120 ms 19604 KB Output is correct
21 Correct 53 ms 14584 KB Output is correct
22 Partially correct 42 ms 13220 KB Partially correct
23 Partially correct 47 ms 14416 KB Partially correct
24 Partially correct 48 ms 14284 KB Partially correct
25 Correct 46 ms 13784 KB Output is correct
26 Partially correct 42 ms 13288 KB Partially correct
27 Partially correct 47 ms 14496 KB Partially correct
28 Partially correct 64 ms 14468 KB Partially correct
29 Partially correct 91 ms 16284 KB Partially correct
30 Correct 136 ms 20832 KB Output is correct
31 Correct 54 ms 15920 KB Output is correct
32 Partially correct 73 ms 14492 KB Partially correct
33 Partially correct 59 ms 14796 KB Partially correct
34 Correct 72 ms 15256 KB Output is correct
35 Correct 52 ms 14816 KB Output is correct
36 Correct 74 ms 15208 KB Output is correct
37 Correct 94 ms 16512 KB Output is correct
38 Partially correct 74 ms 16288 KB Partially correct
39 Partially correct 76 ms 16264 KB Partially correct
40 Correct 145 ms 19904 KB Output is correct
41 Partially correct 176 ms 25012 KB Partially correct