oj.uz

Submission #155928

# Submission time Handle Problem Language Result Execution time Memory
155928 2019-10-02T05:27:35 Z Akashi 007 (CEOI14_007) C++14
30 / 100
 359 ms 25220 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
bool viz[200005];
int s, d, a, b;
int da[200005], db[200005], ds[200005], dd[200005];
queue <int> q;
vector <int> v[200005];

void bfs(int nod, int d[]){
    for(int i = 1; i <= n ; ++i) d[i] = 1e9;
    memset(viz, 0, sizeof(viz));

    q.push(nod);
    d[nod] = 0; viz[nod] = 1;
    while(!q.empty()){
        int nod = q.front();
        q.pop();

        for(auto it : v[nod]){
            if(viz[it]) continue ;
            q.push(it);
            viz[it] = 1;
            d[it] = d[nod] + 1;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &s, &d, &a, &b);

    int x, y;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    bfs(a, da);
    bfs(b, db);
    bfs(s, ds);
    bfs(d, dd);

    if(dd[b] < ds[b] || dd[a] < ds[a]){
        printf("-1");
        return 0;
    }

    int tmp = -1;
    if(dd[b] - ds[b] != dd[a] - ds[a])
        tmp = min(dd[b] - ds[b], dd[a] - ds[a]);
    else{
        tmp = min(dd[b] - ds[b], dd[a] - ds[a]) - 1;
    }
    printf("%d", tmp);

    return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
007.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &s, &d, &a, &b);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:37: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 6 ms 5244 KB Output is correct
2 Partially correct 6 ms 5240 KB Partially correct
3 Partially correct 6 ms 5240 KB Partially correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 6 ms 5240 KB Output is correct
6 Partially correct 6 ms 5240 KB Partially correct
7 Partially correct 6 ms 5240 KB Partially correct
8 Correct 7 ms 5196 KB Output is correct
9 Partially correct 7 ms 5276 KB Partially correct
10 Correct 7 ms 5244 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Correct 7 ms 5240 KB Output is correct
13 Partially correct 7 ms 5244 KB Partially correct
14 Correct 7 ms 5316 KB Output is correct
15 Partially correct 7 ms 5240 KB Partially correct
16 Correct 7 ms 5240 KB Output is correct
17 Correct 7 ms 5240 KB Output is correct
18 Correct 7 ms 5240 KB Output is correct
19 Partially correct 7 ms 5240 KB Partially correct
20 Partially correct 7 ms 5244 KB Partially correct
21 Correct 7 ms 5240 KB Output is correct
22 Partially correct 7 ms 5240 KB Partially correct
23 Partially correct 7 ms 5240 KB Partially correct
24 Correct 7 ms 5240 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 37 ms 7664 KB Partially correct
2 Correct 45 ms 8696 KB Output is correct
3 Partially correct 39 ms 7800 KB Partially correct
4 Correct 57 ms 8800 KB Output is correct
5 Correct 36 ms 7544 KB Output is correct
6 Correct 36 ms 7800 KB Output is correct
7 Partially correct 41 ms 8056 KB Partially correct
8 Partially correct 43 ms 8184 KB Partially correct
9 Correct 56 ms 8952 KB Output is correct
10 Partially correct 191 ms 17528 KB Partially correct
11 Correct 120 ms 10616 KB Output is correct
12 Partially correct 159 ms 12152 KB Partially correct
13 Correct 88 ms 11000 KB Output is correct
14 Correct 85 ms 10060 KB Output is correct
15 Partially correct 175 ms 12024 KB Partially correct
16 Correct 119 ms 12408 KB Output is correct
17 Partially correct 111 ms 11640 KB Partially correct
18 Correct 102 ms 11640 KB Output is correct
19 Partially correct 212 ms 14280 KB Partially correct
20 Correct 247 ms 19960 KB Output is correct
21 Correct 201 ms 14796 KB Output is correct
22 Partially correct 190 ms 13604 KB Partially correct
23 Partially correct 177 ms 14576 KB Partially correct
24 Partially correct 164 ms 14456 KB Partially correct
25 Correct 167 ms 14072 KB Output is correct
26 Partially correct 144 ms 13524 KB Partially correct
27 Partially correct 171 ms 14684 KB Partially correct
28 Partially correct 195 ms 14684 KB Partially correct
29 Partially correct 202 ms 16504 KB Partially correct
30 Correct 281 ms 20972 KB Output is correct
31 Correct 218 ms 16248 KB Output is correct
32 Partially correct 188 ms 14712 KB Partially correct
33 Partially correct 188 ms 15144 KB Partially correct
34 Correct 223 ms 15536 KB Output is correct
35 Correct 169 ms 15132 KB Output is correct
36 Correct 195 ms 15368 KB Output is correct
37 Correct 227 ms 16828 KB Output is correct
38 Partially correct 234 ms 16552 KB Partially correct
39 Partially correct 247 ms 16544 KB Partially correct
40 Correct 270 ms 20216 KB Output is correct
41 Partially correct 359 ms 25220 KB Partially correct