oj.uz

Submission #101446

# Submission time Handle Problem Language Result Execution time Memory
101446 2019-03-19T02:14:50 Z cheeheng 007 (CEOI14_007) C++14
30 / 100
 393 ms 15932 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> AdjList[200005];
int dist[200005];

int main(){
    int N, M;
    int s, d, a, b;
    scanf("%d%d%d%d%d%d", &N, &M, &s, &d, &a, &b);

    for(int i = 0; i < M; i ++){
        int x, y;
        scanf("%d%d", &x, &y);
        AdjList[x].push_back(y);
        AdjList[y].push_back(x);
    }

    memset(dist, -1, sizeof(dist));
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: AdjList[u]){
            if(dist[v] == -1){
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    int sa = dist[a];
    int sb = dist[b];

    memset(dist, -1, sizeof(dist));
    q = queue<int>();
    q.push(d);
    dist[d] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v: AdjList[u]){
            if(dist[v] == -1){
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    int da = dist[a];
    int db = dist[b];

    //printf("%d %d %d %d\n", sa, sb, da, db);

    int resA = min(da-sa, db-sa-1);
    int resB = min(da-sb-1, da-sb);
    int res = max(resA, resB);
    int ans = max(res, -1);
    printf("%d", ans);
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d%d", &N, &M, &s, &d, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5888 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Partially correct 9 ms 5760 KB Partially correct
4 Correct 7 ms 5760 KB Output is correct
5 Correct 8 ms 5812 KB Output is correct
6 Partially correct 9 ms 5888 KB Partially correct
7 Partially correct 7 ms 5760 KB Partially correct
8 Correct 9 ms 5760 KB Output is correct
9 Partially correct 7 ms 5888 KB Partially correct
10 Correct 8 ms 5760 KB Output is correct
11 Correct 8 ms 5888 KB Output is correct
12 Correct 7 ms 5888 KB Output is correct
13 Partially correct 8 ms 5760 KB Partially correct
14 Correct 8 ms 5760 KB Output is correct
15 Partially correct 9 ms 5888 KB Partially correct
16 Correct 8 ms 5888 KB Output is correct
17 Correct 8 ms 5760 KB Output is correct
18 Correct 8 ms 5760 KB Output is correct
19 Partially correct 6 ms 5760 KB Partially correct
20 Partially correct 8 ms 5888 KB Partially correct
21 Correct 8 ms 5888 KB Output is correct
22 Partially correct 8 ms 5888 KB Partially correct
23 Partially correct 8 ms 5888 KB Partially correct
24 Correct 10 ms 5888 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 31 ms 7032 KB Partially correct
2 Correct 57 ms 7644 KB Output is correct
3 Partially correct 41 ms 7196 KB Partially correct
4 Correct 60 ms 7672 KB Output is correct
5 Correct 35 ms 7008 KB Output is correct
6 Correct 32 ms 7160 KB Output is correct
7 Partially correct 40 ms 7288 KB Partially correct
8 Partially correct 36 ms 7288 KB Partially correct
9 Correct 68 ms 7672 KB Output is correct
10 Partially correct 195 ms 11896 KB Partially correct
11 Correct 70 ms 8568 KB Output is correct
12 Partially correct 97 ms 9520 KB Partially correct
13 Correct 74 ms 8824 KB Output is correct
14 Correct 57 ms 8544 KB Output is correct
15 Partially correct 110 ms 9456 KB Partially correct
16 Correct 112 ms 9720 KB Output is correct
17 Partially correct 89 ms 9296 KB Partially correct
18 Correct 116 ms 9292 KB Output is correct
19 Partially correct 130 ms 10488 KB Partially correct
20 Correct 279 ms 13348 KB Output is correct
21 Correct 132 ms 10876 KB Output is correct
22 Partially correct 133 ms 10104 KB Partially correct
23 Correct 127 ms 10720 KB Output is correct
24 Partially correct 139 ms 10800 KB Partially correct
25 Correct 190 ms 10488 KB Output is correct
26 Correct 129 ms 10232 KB Output is correct
27 Partially correct 179 ms 10784 KB Partially correct
28 Partially correct 180 ms 10876 KB Partially correct
29 Partially correct 235 ms 11640 KB Partially correct
30 Correct 320 ms 13816 KB Output is correct
31 Correct 179 ms 11512 KB Output is correct
32 Partially correct 209 ms 10744 KB Partially correct
33 Correct 144 ms 10972 KB Output is correct
34 Correct 151 ms 11256 KB Output is correct
35 Correct 139 ms 11000 KB Output is correct
36 Correct 173 ms 11256 KB Output is correct
37 Correct 238 ms 11956 KB Output is correct
38 Partially correct 180 ms 11908 KB Partially correct
39 Partially correct 208 ms 11896 KB Partially correct
40 Correct 260 ms 13492 KB Output is correct
41 Partially correct 393 ms 15932 KB Partially correct