oj.uz

답안 #101649

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101649 2019-03-19T07:11:15 Z dwsc 007 (CEOI14_007) C++14
0 / 100
 743 ms 27464 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++;
                }
                cout << dist2[a]-dist1[a]-(num2+dist2[a]-dist1[a]<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++){
                         ~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Incorrect 2 ms 384 KB Output isn't correct
5 Incorrect 2 ms 256 KB Output isn't correct
6 Correct 3 ms 256 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Incorrect 2 ms 256 KB Output isn't correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Incorrect 2 ms 384 KB Output isn't correct
13 Correct 2 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 3 ms 384 KB Output isn't correct
17 Incorrect 3 ms 384 KB Output isn't correct
18 Incorrect 3 ms 384 KB Output isn't correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 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 2 ms 384 KB Output is correct
24 Incorrect 4 ms 384 KB Output isn't correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 3648 KB Output is correct
2 Incorrect 65 ms 4856 KB Output isn't correct
3 Correct 49 ms 3832 KB Output is correct
4 Incorrect 80 ms 5140 KB Output isn't correct
5 Correct 55 ms 3448 KB Output is correct
6 Correct 53 ms 3960 KB Output is correct
7 Correct 57 ms 4088 KB Output is correct
8 Correct 59 ms 4216 KB Output is correct
9 Incorrect 91 ms 5492 KB Output isn't correct
10 Correct 532 ms 19076 KB Output is correct
11 Incorrect 110 ms 7236 KB Output isn't correct
12 Correct 167 ms 8952 KB Output is correct
13 Incorrect 121 ms 7672 KB Output isn't correct
14 Correct 95 ms 6524 KB Output is correct
15 Correct 188 ms 8984 KB Output is correct
16 Correct 157 ms 9208 KB Output is correct
17 Correct 126 ms 8316 KB Output is correct
18 Incorrect 227 ms 8440 KB Output isn't correct
19 Correct 246 ms 12280 KB Output is correct
20 Incorrect 515 ms 21372 KB Output isn't correct
21 Incorrect 260 ms 12280 KB Output isn't correct
22 Correct 235 ms 10872 KB Output is correct
23 Correct 238 ms 12088 KB Output is correct
24 Correct 231 ms 12048 KB Output is correct
25 Incorrect 179 ms 11388 KB Output isn't correct
26 Correct 177 ms 11016 KB Output is correct
27 Correct 237 ms 12280 KB Output is correct
28 Correct 247 ms 12408 KB Output is correct
29 Correct 384 ms 15600 KB Output is correct
30 Incorrect 556 ms 22520 KB Output isn't correct
31 Incorrect 267 ms 13924 KB Output isn't correct
32 Correct 253 ms 12280 KB Output is correct
33 Correct 230 ms 12536 KB Output is correct
34 Incorrect 248 ms 13296 KB Output isn't correct
35 Incorrect 247 ms 12792 KB Output isn't correct
36 Incorrect 224 ms 13048 KB Output isn't correct
37 Correct 287 ms 14712 KB Output is correct
38 Correct 283 ms 14428 KB Output is correct
39 Correct 380 ms 14428 KB Output is correct
40 Incorrect 445 ms 20088 KB Output isn't correct
41 Correct 743 ms 27464 KB Output is correct