Submission #793334

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
793334	2023-07-25T17:58:42 Z	Valaki2	007 (CEOI14_007)	C++14	0 / 100	168 ms	17576 KB

007

#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;
    }
    
}

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

Subtask #1

0.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Incorrect	4 ms	5024 KB	Unexpected end of file - int64 expected
3	Incorrect	2 ms	4936 KB	Unexpected end of file - int64 expected
4	Incorrect	2 ms	4948 KB	Unexpected end of file - int64 expected
5	Incorrect	2 ms	5016 KB	Unexpected end of file - int64 expected
6	Incorrect	2 ms	5020 KB	Unexpected end of file - int64 expected
7	Incorrect	2 ms	4948 KB	Unexpected end of file - int64 expected
8	Incorrect	2 ms	5000 KB	Unexpected end of file - int64 expected
9	Incorrect	3 ms	4948 KB	Unexpected end of file - int64 expected
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	2 ms	5024 KB	Output is correct
12	Incorrect	3 ms	4948 KB	Unexpected end of file - int64 expected
13	Incorrect	3 ms	5024 KB	Unexpected end of file - int64 expected
14	Incorrect	2 ms	5020 KB	Unexpected end of file - int64 expected
15	Incorrect	3 ms	4948 KB	Unexpected end of file - int64 expected
16	Incorrect	3 ms	4948 KB	Unexpected end of file - int64 expected
17	Incorrect	2 ms	4948 KB	Unexpected end of file - int64 expected
18	Incorrect	3 ms	5020 KB	Unexpected end of file - int64 expected
19	Incorrect	3 ms	5076 KB	Unexpected end of file - int64 expected
20	Incorrect	2 ms	5020 KB	Unexpected end of file - int64 expected
21	Correct	2 ms	5024 KB	Output is correct
22	Incorrect	2 ms	4948 KB	Unexpected end of file - int64 expected
23	Incorrect	2 ms	4948 KB	Unexpected end of file - int64 expected
24	Incorrect	3 ms	5028 KB	Unexpected end of file - int64 expected

Subtask #2

0.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	7212 KB	Unexpected end of file - int64 expected
2	Incorrect	18 ms	8148 KB	Unexpected end of file - int64 expected
3	Incorrect	16 ms	7380 KB	Unexpected end of file - int64 expected
4	Incorrect	17 ms	8208 KB	Unexpected end of file - int64 expected
5	Correct	15 ms	7208 KB	Output is correct
6	Correct	13 ms	7428 KB	Output is correct
7	Incorrect	16 ms	7592 KB	Unexpected end of file - int64 expected
8	Incorrect	18 ms	7636 KB	Unexpected end of file - int64 expected
9	Incorrect	25 ms	8108 KB	Unexpected end of file - int64 expected
10	Incorrect	90 ms	12492 KB	Unexpected end of file - int64 expected
11	Incorrect	29 ms	9576 KB	Unexpected end of file - int64 expected
12	Incorrect	42 ms	10672 KB	Unexpected end of file - int64 expected
13	Incorrect	32 ms	9936 KB	Unexpected end of file - int64 expected
14	Correct	25 ms	9268 KB	Output is correct
15	Incorrect	35 ms	10772 KB	Unexpected end of file - int64 expected
16	Correct	37 ms	11124 KB	Output is correct
17	Incorrect	34 ms	10496 KB	Unexpected end of file - int64 expected
18	Incorrect	34 ms	10496 KB	Unexpected end of file - int64 expected
19	Incorrect	59 ms	11620 KB	Unexpected end of file - int64 expected
20	Incorrect	160 ms	14492 KB	Unexpected end of file - int64 expected
21	Incorrect	47 ms	12936 KB	Unexpected end of file - int64 expected
22	Incorrect	44 ms	11804 KB	Unexpected end of file - int64 expected
23	Incorrect	53 ms	12824 KB	Unexpected end of file - int64 expected
24	Incorrect	46 ms	12708 KB	Unexpected end of file - int64 expected
25	Incorrect	79 ms	12296 KB	Unexpected end of file - int64 expected
26	Incorrect	57 ms	11936 KB	Unexpected end of file - int64 expected
27	Incorrect	58 ms	12860 KB	Unexpected end of file - int64 expected
28	Incorrect	60 ms	12920 KB	Unexpected end of file - int64 expected
29	Incorrect	84 ms	13352 KB	Unexpected end of file - int64 expected
30	Incorrect	143 ms	15344 KB	Unexpected end of file - int64 expected
31	Incorrect	62 ms	13964 KB	Unexpected end of file - int64 expected
32	Incorrect	57 ms	12748 KB	Unexpected end of file - int64 expected
33	Incorrect	59 ms	13004 KB	Unexpected end of file - int64 expected
34	Incorrect	58 ms	13348 KB	Unexpected end of file - int64 expected
35	Incorrect	47 ms	13060 KB	Unexpected end of file - int64 expected
36	Incorrect	52 ms	13308 KB	Unexpected end of file - int64 expected
37	Correct	64 ms	14212 KB	Output is correct
38	Incorrect	58 ms	13984 KB	Unexpected end of file - int64 expected
39	Incorrect	67 ms	13900 KB	Unexpected end of file - int64 expected
40	Incorrect	108 ms	15392 KB	Unexpected end of file - int64 expected
41	Incorrect	168 ms	17576 KB	Unexpected end of file - int64 expected