oj.uz

Submission #65042

# Submission time Handle Problem Language Result Execution time Memory
65042 2018-08-06T13:38:09 Z bazsi700 007 (CEOI14_007) C++14
0 / 100
 548 ms 17604 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+5) {
            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 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Incorrect 3 ms 504 KB Output isn't correct
5 Incorrect 3 ms 620 KB Output isn't correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 3 ms 624 KB Output is correct
8 Incorrect 3 ms 624 KB Output isn't correct
9 Correct 3 ms 624 KB Output is correct
10 Correct 4 ms 624 KB Output is correct
11 Correct 4 ms 624 KB Output is correct
12 Incorrect 3 ms 624 KB Output isn't correct
13 Correct 4 ms 624 KB Output is correct
14 Incorrect 2 ms 624 KB Output isn't correct
15 Correct 2 ms 624 KB Output is correct
16 Incorrect 3 ms 624 KB Output isn't correct
17 Incorrect 3 ms 624 KB Output isn't correct
18 Incorrect 4 ms 624 KB Output isn't correct
19 Correct 2 ms 624 KB Output is correct
20 Correct 2 ms 624 KB Output is correct
21 Correct 4 ms 624 KB Output is correct
22 Correct 3 ms 624 KB Output is correct
23 Correct 3 ms 624 KB Output is correct
24 Incorrect 4 ms 748 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3452 KB Output is correct
2 Incorrect 61 ms 4860 KB Output isn't correct
3 Correct 43 ms 4860 KB Output is correct
4 Incorrect 61 ms 4984 KB Output isn't correct
5 Correct 38 ms 4984 KB Output is correct
6 Correct 38 ms 4984 KB Output is correct
7 Correct 57 ms 4984 KB Output is correct
8 Correct 44 ms 4984 KB Output is correct
9 Incorrect 84 ms 4984 KB Output isn't correct
10 Correct 268 ms 9352 KB Output is correct
11 Incorrect 127 ms 9352 KB Output isn't correct
12 Correct 152 ms 9352 KB Output is correct
13 Incorrect 158 ms 9352 KB Output isn't correct
14 Correct 79 ms 9352 KB Output is correct
15 Correct 148 ms 9352 KB Output is correct
16 Correct 149 ms 9352 KB Output is correct
17 Correct 154 ms 9352 KB Output is correct
18 Incorrect 185 ms 9352 KB Output isn't correct
19 Correct 248 ms 9740 KB Output is correct
20 Incorrect 319 ms 12540 KB Output isn't correct
21 Incorrect 200 ms 12540 KB Output isn't correct
22 Correct 202 ms 12540 KB Output is correct
23 Correct 195 ms 12540 KB Output is correct
24 Correct 154 ms 12540 KB Output is correct
25 Incorrect 175 ms 12540 KB Output isn't correct
26 Correct 166 ms 12540 KB Output is correct
27 Correct 169 ms 12540 KB Output is correct
28 Correct 197 ms 12540 KB Output is correct
29 Correct 258 ms 12540 KB Output is correct
30 Incorrect 381 ms 13692 KB Output isn't correct
31 Incorrect 243 ms 13692 KB Output isn't correct
32 Correct 191 ms 13692 KB Output is correct
33 Correct 177 ms 13692 KB Output is correct
34 Incorrect 233 ms 13692 KB Output isn't correct
35 Incorrect 171 ms 13692 KB Output isn't correct
36 Incorrect 181 ms 13692 KB Output isn't correct
37 Correct 212 ms 14460 KB Output is correct
38 Correct 225 ms 14460 KB Output is correct
39 Correct 317 ms 14460 KB Output is correct
40 Incorrect 390 ms 15428 KB Output isn't correct
41 Correct 548 ms 17604 KB Output is correct