oj.uz

Submission #793400

# Submission time Handle Problem Language Result Execution time Memory
793400 2023-07-25T19:10:03 Z Valaki2 007 (CEOI14_007) C++14
43.3333 / 100
 173 ms 17484 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[g] += to_add;
    db[g] += to_add;
    for(int i = 1; i <= n; i++) {
        if(i != g) {
            dg[i] += to_add;
        }
    }
    int closest_g = n + 1, closest_s = n + 1;
    if(da[s] != db[s] || da[g] != db[g]) {
        exit(1);
    }
    if(da[s] != da[g] || db[s] != 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 max_dab = max(da[cur], db[cur]);
        int min_dab = min(da[cur], db[cur]);
        if(max_dab + dg[cur] == max(da[g], db[g])) {
            if(min_dab + dg[cur] == min(da[g], db[g])) {
                closest_g = min(closest_g, max_dab);
            }
        }
        if(max_dab + ds[cur] == max(da[s], db[s])) {
            if(min_dab + ds[cur] == min(da[s], db[s])) {
                closest_s = min(closest_s, max_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
13.0 / 30.0

# Verdict Execution time Memory 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 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Partially correct 2 ms 5016 KB Partially correct
7 Correct 2 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 2 ms 4948 KB Output is correct
10 Correct 2 ms 4948 KB Output is correct
11 Correct 2 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 2 ms 4948 KB Output is correct
14 Correct 2 ms 4948 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 2 ms 4964 KB Output is correct
18 Correct 2 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 2 ms 4948 KB Output is correct
22 Partially correct 3 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
30.333333 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 6860 KB Output is correct
2 Correct 18 ms 7764 KB Output is correct
3 Correct 19 ms 6940 KB Output is correct
4 Correct 18 ms 7892 KB Output is correct
5 Correct 15 ms 6740 KB Output is correct
6 Correct 17 ms 7076 KB Output is correct
7 Partially correct 19 ms 7256 KB Partially correct
8 Correct 17 ms 7276 KB Output is correct
9 Correct 26 ms 7640 KB Output is correct
10 Correct 100 ms 12064 KB Output is correct
11 Correct 35 ms 9164 KB Output is correct
12 Correct 41 ms 10284 KB Output is correct
13 Correct 33 ms 9548 KB Output is correct
14 Correct 26 ms 8820 KB Output is correct
15 Correct 36 ms 10388 KB Output is correct
16 Correct 38 ms 10676 KB Output is correct
17 Correct 43 ms 10068 KB Output is correct
18 Correct 37 ms 10168 KB Output is correct
19 Correct 71 ms 11352 KB Output is correct
20 Correct 115 ms 14192 KB Output is correct
21 Correct 49 ms 12488 KB Output is correct
22 Correct 67 ms 11436 KB Output is correct
23 Runtime error 46 ms 12368 KB Execution failed because the return code was nonzero
24 Correct 47 ms 12336 KB Output is correct
25 Correct 52 ms 11968 KB Output is correct
26 Runtime error 44 ms 11516 KB Execution failed because the return code was nonzero
27 Correct 50 ms 12516 KB Output is correct
28 Correct 71 ms 12452 KB Output is correct
29 Correct 79 ms 12936 KB Output is correct
30 Correct 127 ms 14968 KB Output is correct
31 Correct 77 ms 13688 KB Output is correct
32 Correct 56 ms 12340 KB Output is correct
33 Runtime error 52 ms 12620 KB Execution failed because the return code was nonzero
34 Correct 78 ms 12988 KB Output is correct
35 Correct 51 ms 12748 KB Output is correct
36 Correct 90 ms 13012 KB Output is correct
37 Correct 72 ms 14076 KB Output is correct
38 Correct 62 ms 13904 KB Output is correct
39 Correct 69 ms 13856 KB Output is correct
40 Correct 131 ms 15536 KB Output is correct
41 Correct 173 ms 17484 KB Output is correct