oj.uz

답안 #101650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
101650 2019-03-19T07:11:53 Z dwsc 007 (CEOI14_007) C++14
3 / 100
 711 ms 26744 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
3.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Partially correct 2 ms 384 KB Partially 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 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 256 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 3 ms 384 KB Output isn't correct
19 Correct 0 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 3 ms 384 KB Output is correct
24 Correct 3 ms 380 KB Output is correct

Subtask #2
0.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 3192 KB Output is correct
2 Incorrect 65 ms 4444 KB Output isn't correct
3 Correct 68 ms 3448 KB Output is correct
4 Incorrect 78 ms 4604 KB Output isn't correct
5 Correct 73 ms 3192 KB Output is correct
6 Correct 50 ms 3544 KB Output is correct
7 Correct 60 ms 3832 KB Output is correct
8 Correct 53 ms 3832 KB Output is correct
9 Incorrect 104 ms 5264 KB Output isn't correct
10 Correct 417 ms 18352 KB Output is correct
11 Incorrect 135 ms 6776 KB Output isn't correct
12 Correct 189 ms 8524 KB Output is correct
13 Incorrect 127 ms 7288 KB Output isn't correct
14 Correct 115 ms 6152 KB Output is correct
15 Correct 201 ms 8544 KB Output is correct
16 Correct 160 ms 8952 KB Output is correct
17 Correct 158 ms 7952 KB Output is correct
18 Incorrect 166 ms 8056 KB Output isn't correct
19 Correct 238 ms 11700 KB Output is correct
20 Incorrect 612 ms 20600 KB Output isn't correct
21 Incorrect 213 ms 11740 KB Output isn't correct
22 Correct 198 ms 10144 KB Output is correct
23 Correct 200 ms 11448 KB Output is correct
24 Correct 220 ms 11500 KB Output is correct
25 Incorrect 196 ms 10788 KB Output isn't correct
26 Correct 180 ms 10360 KB Output is correct
27 Correct 223 ms 11640 KB Output is correct
28 Correct 233 ms 11640 KB Output is correct
29 Correct 317 ms 14840 KB Output is correct
30 Incorrect 510 ms 21784 KB Output isn't correct
31 Incorrect 240 ms 13532 KB Output isn't correct
32 Correct 217 ms 11640 KB Output is correct
33 Correct 193 ms 11896 KB Output is correct
34 Incorrect 299 ms 12756 KB Output isn't correct
35 Incorrect 230 ms 12024 KB Output isn't correct
36 Incorrect 218 ms 12408 KB Output isn't correct
37 Correct 318 ms 14200 KB Output is correct
38 Correct 268 ms 13688 KB Output is correct
39 Correct 316 ms 13800 KB Output is correct
40 Incorrect 480 ms 19164 KB Output isn't correct
41 Correct 711 ms 26744 KB Output is correct