oj.uz

Submission #793361

# Submission time Handle Problem Language Result Execution time Memory
793361 2023-07-25T18:23:17 Z Valaki2 007 (CEOI14_007) C++14
10 / 100
 224 ms 17740 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 max_dab = max(da[cur], db[cur]), min_dab = min(da[cur], db[cur]);
        if((max_dab + closest_g == max(da[g], db[g])) && (min_dab + closest_g == min(da[g], db[g]))) {
            closest_g = min(closest_g, max_dab);
        }
        if((max_dab + closest_s == max(da[s], db[s]))) {
            closest_s = min(closest_s, max_dab);
        }*/
        int dab = max(da[cur], db[cur]);
        if(dab + dg[cur] == max(da[g], db[g])) {
            closest_g = min(closest_g, dab);
        }
        if(dab + dg[cur] == max(da[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
3.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 2 ms 4948 KB Execution failed because the return code was nonzero
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4940 KB Output is correct
5 Incorrect 2 ms 5024 KB Output isn't correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 2 ms 5020 KB Output is correct
8 Incorrect 2 ms 4948 KB Output isn't correct
9 Correct 2 ms 5020 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 3 ms 5060 KB Output is correct
12 Incorrect 2 ms 4948 KB Output isn't correct
13 Partially correct 2 ms 4948 KB Partially correct
14 Correct 2 ms 5020 KB Output is correct
15 Partially correct 2 ms 4948 KB Partially correct
16 Incorrect 2 ms 5024 KB Output isn't correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 2 ms 5024 KB Output is correct
19 Partially correct 3 ms 4948 KB Partially correct
20 Partially correct 3 ms 5020 KB Partially correct
21 Correct 3 ms 5024 KB Output is correct
22 Partially correct 3 ms 4948 KB Partially correct
23 Partially correct 3 ms 4948 KB Partially correct
24 Correct 3 ms 5076 KB Output is correct

Subtask #2
7.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 15 ms 7280 KB Partially correct
2 Correct 17 ms 8148 KB Output is correct
3 Partially correct 15 ms 7380 KB Partially correct
4 Correct 19 ms 8344 KB Output is correct
5 Correct 16 ms 7132 KB Output is correct
6 Correct 14 ms 7428 KB Output is correct
7 Partially correct 16 ms 7636 KB Partially correct
8 Partially correct 18 ms 7680 KB Partially correct
9 Correct 26 ms 8184 KB Output is correct
10 Partially correct 90 ms 12552 KB Partially correct
11 Incorrect 44 ms 9676 KB Output isn't correct
12 Partially correct 39 ms 10744 KB Partially correct
13 Incorrect 33 ms 10064 KB Output isn't correct
14 Correct 26 ms 9312 KB Output is correct
15 Correct 37 ms 10956 KB Output is correct
16 Correct 39 ms 11252 KB Output is correct
17 Correct 35 ms 10532 KB Output is correct
18 Correct 36 ms 10596 KB Output is correct
19 Partially correct 60 ms 11808 KB Partially correct
20 Correct 129 ms 14684 KB Output is correct
21 Incorrect 71 ms 13084 KB Output isn't correct
22 Partially correct 45 ms 12040 KB Partially correct
23 Runtime error 58 ms 12908 KB Execution failed because the return code was nonzero
24 Partially correct 47 ms 12900 KB Partially correct
25 Correct 55 ms 12424 KB Output is correct
26 Runtime error 45 ms 12100 KB Execution failed because the return code was nonzero
27 Partially correct 53 ms 13068 KB Partially correct
28 Partially correct 54 ms 12972 KB Partially correct
29 Partially correct 87 ms 13436 KB Partially correct
30 Correct 134 ms 15444 KB Output is correct
31 Correct 58 ms 14204 KB Output is correct
32 Partially correct 53 ms 12876 KB Partially correct
33 Runtime error 68 ms 13236 KB Execution failed because the return code was nonzero
34 Correct 69 ms 13584 KB Output is correct
35 Incorrect 49 ms 13288 KB Output isn't correct
36 Correct 54 ms 13352 KB Output is correct
37 Correct 77 ms 14476 KB Output is correct
38 Partially correct 71 ms 14280 KB Partially correct
39 Partially correct 68 ms 14160 KB Partially correct
40 Correct 108 ms 15668 KB Output is correct
41 Partially correct 224 ms 17740 KB Partially correct