oj.uz

Submission #101476

# Submission time Handle Problem Language Result Execution time Memory
101476 2019-03-19T03:00:45 Z dwsc 007 (CEOI14_007) C++14
0 / 100
 725 ms 53320 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){
                    fin1s = p1[fin1s];
                    fin2s = p1[fin2s];
                    num1++;
                }
                while (fin1d != fin2d){
                    fin1d = p2[fin1d];
                    fin2d = p2[fin2d];
                    num2++;
                }
              	if (num2 == num1) cout << 1/0;
                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:77:43: warning: division by zero [-Wdiv-by-zero]
                if (num2 == num1) cout << 1/0;
                                          ~^~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Runtime error 2 ms 384 KB Execution killed with signal 8 (could be triggered by violating memory limits)
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Runtime error 3 ms 384 KB Execution killed with signal 8 (could be triggered by violating memory limits)
8 Correct 2 ms 256 KB Output is correct
9 Runtime error 2 ms 384 KB Execution killed with signal 8 (could be triggered by violating memory limits)
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Runtime error 3 ms 512 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Incorrect 1 ms 384 KB Output isn't correct
15 Correct 3 ms 256 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Runtime error 3 ms 512 KB Execution killed with signal 8 (could be triggered by violating memory limits)
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 2 ms 384 KB Output is correct
23 Runtime error 4 ms 640 KB Execution killed with signal 8 (could be triggered by violating memory limits)
24 Correct 4 ms 384 KB Output is correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3272 KB Output is correct
2 Correct 78 ms 4428 KB Output is correct
3 Runtime error 74 ms 6704 KB Execution killed with signal 8 (could be triggered by violating memory limits)
4 Correct 70 ms 4600 KB Output is correct
5 Correct 76 ms 3192 KB Output is correct
6 Correct 63 ms 3448 KB Output is correct
7 Correct 64 ms 3704 KB Output is correct
8 Correct 59 ms 3832 KB Output is correct
9 Correct 99 ms 5156 KB Output is correct
10 Runtime error 426 ms 36148 KB Execution killed with signal 8 (could be triggered by violating memory limits)
11 Correct 125 ms 6776 KB Output is correct
12 Runtime error 149 ms 17076 KB Execution killed with signal 8 (could be triggered by violating memory limits)
13 Correct 120 ms 7288 KB Output is correct
14 Correct 112 ms 6152 KB Output is correct
15 Correct 147 ms 8568 KB Output is correct
16 Correct 152 ms 9016 KB Output is correct
17 Correct 123 ms 8040 KB Output is correct
18 Correct 142 ms 8056 KB Output is correct
19 Runtime error 261 ms 23300 KB Execution killed with signal 8 (could be triggered by violating memory limits)
20 Correct 503 ms 20604 KB Output is correct
21 Correct 214 ms 11628 KB Output is correct
22 Runtime error 187 ms 20188 KB Execution killed with signal 8 (could be triggered by violating memory limits)
23 Correct 250 ms 11512 KB Output is correct
24 Runtime error 242 ms 22648 KB Execution killed with signal 8 (could be triggered by violating memory limits)
25 Correct 218 ms 10872 KB Output is correct
26 Correct 183 ms 10232 KB Output is correct
27 Correct 265 ms 11640 KB Output is correct
28 Correct 332 ms 11632 KB Output is correct
29 Runtime error 294 ms 29304 KB Execution killed with signal 8 (could be triggered by violating memory limits)
30 Correct 524 ms 21856 KB Output is correct
31 Correct 244 ms 13304 KB Output is correct
32 Runtime error 272 ms 23304 KB Execution killed with signal 8 (could be triggered by violating memory limits)
33 Correct 233 ms 12024 KB Output is correct
34 Correct 312 ms 12700 KB Output is correct
35 Correct 290 ms 12160 KB Output is correct
36 Correct 258 ms 12664 KB Output is correct
37 Correct 313 ms 14064 KB Output is correct
38 Correct 301 ms 13688 KB Output is correct
39 Correct 306 ms 13944 KB Output is correct
40 Correct 480 ms 19320 KB Output is correct
41 Runtime error 725 ms 53320 KB Execution killed with signal 8 (could be triggered by violating memory limits)