oj.uz

Submission #101459

# Submission time Handle Problem Language Result Execution time Memory
101459 2019-03-19T02:41:09 Z dwsc 007 (CEOI14_007) C++14
0 / 100
 626 ms 25464 KB 
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<int> adj[m];
    int s,d,a,b;
    cin >> s >> d >> a >> b;
    s--;
    d--;
    a--;
    b--;
    for (int i = 0; i < m; i++){
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    queue<int> q;
    int dist1[n],dist2[n];
    memset(dist1,-1,sizeof(dist1));
    memset(dist2,-1,sizeof(dist2));
    dist1[s] = 0;
    dist2[d] = 0;
    q.push(s);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i];
            if (dist1[v] == -1){
                dist1[v] = dist1[u]+1;
                q.push(v);
            }
        }
    }
    q.push(d);
    while (!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i];
            if (dist2[v] == -1){
                dist2[v] = dist2[u]+1;
                q.push(v);
            }
        }
    }
   // cout << dist1[a] << " " << dist1[b] << "\n";
   // cout << dist2[a] << " " << dist2[b] << "\n";
    if (dist2[a] < dist1[a] && dist2[b] < dist1[b]) cout << -1;
    else{
        if (dist1[a] > dist1[b]){
            swap(dist1[a],dist1[b]);
            swap(dist2[a],dist2[b]);
        }
        if (dist1[a] == dist1[b]){
            if (dist2[a] == dist2[b]) cout << dist2[a] - dist1[a];
            else if (dist2[a]+1 == dist2[b]) cout << dist2[a] - dist1[a];
            else cout << dist2[b] - dist1[b];
        }
        else if (dist1[a]+1 == dist1[b]){
            if (dist2[a] == dist2[b]) cout << dist2[b] - dist1[b];
            else if (dist2[a] +1 == dist2[b]) cout << dist2[a] - dist1[a];
            else cout << dist2[b] - dist1[b];
        }
    }
}/*
6 6
1 2 3 4
1 5
5 6
6 3
6 4
1 2
3 4

6 7
5 6 1 2
6 3
1 2
1 3
2 3
1 5
2 4
5 4
*/

Compilation message

007.cpp: In function 'int main()':
007.cpp:31:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:43:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3064 KB Output is correct
2 Incorrect 69 ms 4108 KB Output isn't correct
3 Correct 65 ms 3064 KB Output is correct
4 Incorrect 87 ms 4216 KB Output isn't correct
5 Correct 47 ms 2808 KB Output is correct
6 Correct 68 ms 3320 KB Output is correct
7 Correct 52 ms 3320 KB Output is correct
8 Correct 71 ms 3388 KB Output is correct
9 Incorrect 98 ms 4648 KB Output isn't correct
10 Correct 400 ms 17784 KB Output is correct
11 Incorrect 109 ms 6136 KB Output isn't correct
12 Correct 157 ms 7672 KB Output is correct
13 Incorrect 134 ms 6520 KB Output isn't correct
14 Correct 83 ms 5496 KB Output is correct
15 Correct 120 ms 7544 KB Output is correct
16 Correct 168 ms 8100 KB Output is correct
17 Correct 177 ms 7276 KB Output is correct
18 Incorrect 133 ms 7160 KB Output isn't correct
19 Correct 249 ms 10872 KB Output is correct
20 Incorrect 491 ms 19656 KB Output isn't correct
21 Incorrect 192 ms 10360 KB Output isn't correct
22 Correct 206 ms 9160 KB Output is correct
23 Correct 185 ms 10232 KB Output is correct
24 Correct 189 ms 10072 KB Output is correct
25 Incorrect 200 ms 9648 KB Output isn't correct
26 Correct 168 ms 9208 KB Output is correct
27 Correct 231 ms 10488 KB Output is correct
28 Correct 238 ms 10436 KB Output is correct
29 Correct 332 ms 13820 KB Output is correct
30 Incorrect 626 ms 20680 KB Output isn't correct
31 Incorrect 291 ms 12024 KB Output isn't correct
32 Correct 191 ms 10360 KB Output is correct
33 Correct 231 ms 10616 KB Output is correct
34 Incorrect 247 ms 11384 KB Output isn't correct
35 Incorrect 222 ms 10748 KB Output isn't correct
36 Incorrect 213 ms 11204 KB Output isn't correct
37 Correct 250 ms 12536 KB Output is correct
38 Correct 249 ms 12280 KB Output is correct
39 Correct 255 ms 12280 KB Output is correct
40 Incorrect 472 ms 17884 KB Output isn't correct
41 Correct 620 ms 25464 KB Output is correct