oj.uz

답안 #793364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793364 2023-07-25T18:26:00 Z Valaki2 007 (CEOI14_007) C++14
10 / 100
 174 ms 17488 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 max_dab = max(da[cur], db[cur]);
        int min_dab = max(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 + dg[cur] == max(da[s], db[s])) {
            if(min_dab + dg[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
3.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Incorrect 2 ms 4948 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 4948 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 4948 KB Output isn't 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 Incorrect 2 ms 4948 KB Output isn't correct
17 Correct 2 ms 4948 KB Output is correct
18 Correct 4 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 3 ms 4948 KB Partially correct
24 Correct 3 ms 4948 KB Output is correct

Subtask #2
7.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 13 ms 6904 KB Partially correct
2 Correct 17 ms 7804 KB Output is correct
3 Partially correct 15 ms 7012 KB Partially correct
4 Correct 18 ms 7844 KB Output is correct
5 Correct 16 ms 6760 KB Output is correct
6 Correct 14 ms 7132 KB Output is correct
7 Partially correct 16 ms 7300 KB Partially correct
8 Partially correct 16 ms 7252 KB Partially correct
9 Correct 27 ms 7672 KB Output is correct
10 Partially correct 95 ms 12160 KB Partially correct
11 Incorrect 29 ms 9296 KB Output isn't correct
12 Partially correct 39 ms 10304 KB Partially correct
13 Incorrect 37 ms 9496 KB Output isn't correct
14 Correct 27 ms 8860 KB Output is correct
15 Correct 35 ms 10444 KB Output is correct
16 Correct 39 ms 10696 KB Output is correct
17 Correct 32 ms 10060 KB Output is correct
18 Correct 38 ms 10068 KB Output is correct
19 Partially correct 60 ms 11316 KB Partially correct
20 Correct 124 ms 14156 KB Output is correct
21 Incorrect 55 ms 12484 KB Output isn't correct
22 Partially correct 54 ms 11524 KB Partially correct
23 Correct 51 ms 12364 KB Output is correct
24 Partially correct 49 ms 12364 KB Partially correct
25 Correct 48 ms 11952 KB Output is correct
26 Correct 43 ms 11620 KB Output is correct
27 Partially correct 51 ms 12496 KB Partially correct
28 Partially correct 81 ms 12556 KB Partially correct
29 Partially correct 86 ms 12940 KB Partially correct
30 Correct 149 ms 15000 KB Output is correct
31 Correct 58 ms 13644 KB Output is correct
32 Partially correct 64 ms 12364 KB Partially correct
33 Correct 54 ms 12652 KB Output is correct
34 Correct 65 ms 12976 KB Output is correct
35 Incorrect 51 ms 12732 KB Output isn't correct
36 Correct 76 ms 13136 KB Output is correct
37 Correct 72 ms 14044 KB Output is correct
38 Partially correct 65 ms 13944 KB Partially correct
39 Partially correct 100 ms 13916 KB Partially correct
40 Correct 159 ms 15372 KB Output is correct
41 Partially correct 174 ms 17488 KB Partially correct