oj.uz

Submission #65041

# Submission time Handle Problem Language Result Execution time Memory
65041 2018-08-06T13:37:16 Z bazsi700 007 (CEOI14_007) C++14
0 / 100
 426 ms 17388 KB 
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,s,d,a,b;
    cin >> n >> m >> s >> d >> a >> b;
    vector<vector<int> > graph(n+1,vector<int>());
    for(int i = 0; i < m; i++) {
        int x,y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    vector<bool> wass(n+1,false);
    vector<int> dists(n+1,0);
    vector<bool> wasd(n+1,false);
    vector<int> distd(n+1,0);
    vector<bool> wasa(n+1,false);
    vector<int> dista(n+1,0);
    vector<bool> wasb(n+1,false);
    vector<int> distb(n+1,0);
    wass[s] = true;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wass[u]) {
                wass[u] = true;
                q.push(u);
                dists[u] = dists[v]+1;
            }
        }
    }
    wasd[d] = true;
    q.push(d);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wasd[u]) {
                wasd[u] = true;
                q.push(u);
                distd[u] = distd[v]+1;
            }
        }
    }
    wasa[a] = true;
    q.push(a);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wasa[u]) {
                wasa[u] = true;
                q.push(u);
                dista[u] = dista[v]+1;
            }
        }
    }
    wasb[b] = true;
    q.push(b);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(int u : graph[v]) {
            if(!wasb[u]) {
                wasb[u] = true;
                q.push(u);
                distb[u] = distb[v]+1;
            }
        }
    }
    if(dists[a] == dists[b] && distd[a] == distd[b]) {
        int mxdistd = -1;
        int mxdists = -1;
        for(int i = 1; i <= n; i++) {
            if(dista[i] == distb[i]) {
                if(dista[i]+distd[i] == distd[a]) {
                    mxdistd = max(mxdistd,dista[i]);
                }
                if(dista[i]+dists[i] == dists[a]) {
                    mxdists = max(mxdists,dista[i]);
                }
            }
        }
        if(mxdists > mxdistd) {
            cout << max(min(distd[a]-dists[a],distd[b]-dists[b])-1,-1);
        } else {
            cout << max(min(distd[a]-dists[a],distd[b]-dists[b]),-1);
        }
    } else {
        cout << max(min(distd[a]-dists[a],distd[b]-dists[b]),-1);
    }
    return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Incorrect 2 ms 488 KB Output isn't correct
5 Incorrect 3 ms 540 KB Output isn't correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Incorrect 2 ms 540 KB Output isn't correct
9 Correct 2 ms 540 KB Output is correct
10 Correct 2 ms 540 KB Output is correct
11 Correct 3 ms 540 KB Output is correct
12 Incorrect 4 ms 564 KB Output isn't correct
13 Correct 2 ms 620 KB Output is correct
14 Incorrect 3 ms 620 KB Output isn't correct
15 Correct 3 ms 620 KB Output is correct
16 Incorrect 4 ms 624 KB Output isn't correct
17 Incorrect 3 ms 708 KB Output isn't correct
18 Incorrect 3 ms 708 KB Output isn't correct
19 Correct 3 ms 708 KB Output is correct
20 Correct 3 ms 708 KB Output is correct
21 Correct 3 ms 708 KB Output is correct
22 Correct 3 ms 708 KB Output is correct
23 Correct 3 ms 708 KB Output is correct
24 Incorrect 3 ms 708 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3436 KB Output is correct
2 Incorrect 89 ms 4844 KB Output isn't correct
3 Correct 38 ms 4844 KB Output is correct
4 Incorrect 68 ms 4976 KB Output isn't correct
5 Correct 49 ms 4976 KB Output is correct
6 Correct 46 ms 4976 KB Output is correct
7 Correct 36 ms 4976 KB Output is correct
8 Correct 43 ms 4976 KB Output is correct
9 Incorrect 62 ms 4976 KB Output isn't correct
10 Correct 228 ms 9308 KB Output is correct
11 Incorrect 138 ms 9308 KB Output isn't correct
12 Correct 131 ms 9308 KB Output is correct
13 Incorrect 102 ms 9308 KB Output isn't correct
14 Correct 87 ms 9308 KB Output is correct
15 Correct 130 ms 9308 KB Output is correct
16 Correct 128 ms 9308 KB Output is correct
17 Correct 133 ms 9308 KB Output is correct
18 Incorrect 150 ms 9308 KB Output isn't correct
19 Correct 265 ms 9636 KB Output is correct
20 Incorrect 338 ms 12524 KB Output isn't correct
21 Incorrect 182 ms 12524 KB Output isn't correct
22 Correct 158 ms 12524 KB Output is correct
23 Correct 168 ms 12524 KB Output is correct
24 Correct 226 ms 12524 KB Output is correct
25 Incorrect 193 ms 12524 KB Output isn't correct
26 Correct 163 ms 12524 KB Output is correct
27 Correct 204 ms 12524 KB Output is correct
28 Correct 247 ms 12524 KB Output is correct
29 Correct 357 ms 12524 KB Output is correct
30 Incorrect 406 ms 13624 KB Output isn't correct
31 Incorrect 200 ms 13668 KB Output isn't correct
32 Correct 199 ms 13668 KB Output is correct
33 Correct 226 ms 13668 KB Output is correct
34 Incorrect 262 ms 13668 KB Output isn't correct
35 Incorrect 223 ms 13668 KB Output isn't correct
36 Incorrect 187 ms 13668 KB Output isn't correct
37 Correct 196 ms 14460 KB Output is correct
38 Correct 255 ms 14460 KB Output is correct
39 Correct 298 ms 14460 KB Output is correct
40 Incorrect 310 ms 15484 KB Output isn't correct
41 Correct 426 ms 17388 KB Output is correct