oj.uz

Submission #101489

# Submission time Handle Problem Language Result Execution time Memory
101489 2019-03-19T03:12:53 Z dwsc 007 (CEOI14_007) C++14
0 / 100
 796 ms 27284 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 p1[n],p2[n];
    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);
                p1[v] = u;
            }
        }
    }
    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);
                p2[v] = u;
            }

        }
    }
   // 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]){
                int fin1s = a,fin2s = b;
                int fin1d = a,fin2d = b;
                int num1 = 0,num2 = 0;
                while (fin1s != fin2s){
                    for (int i = 0; i < adj[fin1s].size(); i++){
                        if (dist1[adj[fin1s][i]]+1 == dist1[fin1s]){
                            fin1s = adj[fin1s][i];
                            break;
                        }
                    }
                    for (int i = 0; i < adj[fin2s].size(); i++){
                        if (dist1[adj[fin2s][i]]+1 == dist1[fin2s]){
                            fin2s = adj[fin2s][i];
                            break;
                        }
                    }
                    num1++;
                }
                while (fin1d != fin2d){
                     for (int i = 0; i < adj[fin1d].size(); i++){
                        if (dist2[adj[fin1d][i]]+1 == dist2[fin1d]){
                            fin1d = adj[fin1d][i];
                            break;
                        }
                    }
                    for (int i = 0; i < adj[fin2d].size(); i++){
                        if (dist2[adj[fin2d][i]]+1 == dist2[fin2d]){
                            fin2d = adj[fin2d][i];
                            break;
                        }
                    }
                    num2++;
                }
                cout << dist2[a]-dist1[a]-(num2<num1);
            }
            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:32:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:45:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < adj[u].size(); i++){
                         ~~^~~~~~~~~~~~~~~
007.cpp:69:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < adj[fin1s].size(); i++){
                                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:75:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < adj[fin2s].size(); i++){
                                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:84:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                      for (int i = 0; i < adj[fin1d].size(); i++){
                                      ~~^~~~~~~~~~~~~~~~~~~
007.cpp:90:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for (int i = 0; i < adj[fin2d].size(); i++){
                                     ~~^~~~~~~~~~~~~~~~~~~
007.cpp:22:9: warning: variable 'p1' set but not used [-Wunused-but-set-variable]
     int p1[n],p2[n];
         ^~
007.cpp:22:15: warning: variable 'p2' set but not used [-Wunused-but-set-variable]
     int p1[n],p2[n];
               ^~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 3 ms 256 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Incorrect 3 ms 256 KB Output isn't correct
15 Correct 3 ms 384 KB Output is correct
16 Incorrect 3 ms 384 KB Output isn't correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 3 ms 384 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 56 ms 3616 KB Output is correct
2 Correct 69 ms 5100 KB Output is correct
3 Correct 80 ms 3932 KB Output is correct
4 Correct 73 ms 5212 KB Output is correct
5 Correct 46 ms 3628 KB Output is correct
6 Correct 50 ms 3960 KB Output is correct
7 Correct 53 ms 4344 KB Output is correct
8 Correct 57 ms 4344 KB Output is correct
9 Incorrect 91 ms 5624 KB Output isn't correct
10 Correct 488 ms 19152 KB Output is correct
11 Correct 112 ms 7392 KB Output is correct
12 Correct 133 ms 9212 KB Output is correct
13 Correct 106 ms 7928 KB Output is correct
14 Correct 108 ms 6704 KB Output is correct
15 Correct 127 ms 9080 KB Output is correct
16 Correct 171 ms 9720 KB Output is correct
17 Correct 144 ms 8568 KB Output is correct
18 Correct 149 ms 8568 KB Output is correct
19 Correct 265 ms 12712 KB Output is correct
20 Incorrect 515 ms 21468 KB Output isn't correct
21 Correct 228 ms 12632 KB Output is correct
22 Correct 199 ms 11120 KB Output is correct
23 Correct 206 ms 12404 KB Output is correct
24 Correct 219 ms 12280 KB Output is correct
25 Correct 218 ms 11744 KB Output is correct
26 Correct 226 ms 11188 KB Output is correct
27 Correct 216 ms 12652 KB Output is correct
28 Correct 277 ms 12768 KB Output is correct
29 Correct 348 ms 15740 KB Output is correct
30 Incorrect 625 ms 22624 KB Output isn't correct
31 Correct 319 ms 14316 KB Output is correct
32 Correct 216 ms 12668 KB Output is correct
33 Correct 235 ms 12920 KB Output is correct
34 Correct 273 ms 13664 KB Output is correct
35 Correct 209 ms 13048 KB Output is correct
36 Correct 276 ms 13432 KB Output is correct
37 Correct 300 ms 15172 KB Output is correct
38 Correct 261 ms 14712 KB Output is correct
39 Correct 303 ms 14796 KB Output is correct
40 Incorrect 420 ms 20216 KB Output isn't correct
41 Correct 796 ms 27284 KB Output is correct