oj.uz

Submission #155932

# Submission time Handle Problem Language Result Execution time Memory
155932 2019-10-02T05:42:13 Z Akashi 007 (CEOI14_007) C++14
0 / 100
 357 ms 17780 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()
{
//    freopen("1.in", "r", stdin);
    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{
        int dif = min(dd[b] - ds[b], dd[a] - ds[a]), nr1 = 0, nr2 = 0;
        for(int i = 1; i <= n ; ++i)
            if(da[i] == db[i] && da[i] + ds[i] == ds[a]) nr1 = max(nr1, da[i]);

        for(int i = 1; i <= n ; ++i)
            if(da[i] == db[i] && da[i] + dd[i] == ds[a]) nr2 = max(nr2, da[i]);

        if(nr1 > nr2 - dif) 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:33: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:34: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:38: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
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5244 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Partially correct 6 ms 5240 KB Partially correct
4 Incorrect 6 ms 5240 KB Output isn't correct
5 Incorrect 6 ms 5240 KB Output isn't correct
6 Correct 6 ms 5240 KB Output is correct
7 Correct 6 ms 5240 KB Output is correct
8 Incorrect 6 ms 5240 KB Output isn't correct
9 Correct 6 ms 5240 KB Output is correct
10 Correct 6 ms 5240 KB Output is correct
11 Correct 6 ms 5240 KB Output is correct
12 Incorrect 7 ms 5240 KB Output isn't correct
13 Correct 7 ms 5240 KB Output is correct
14 Incorrect 6 ms 5244 KB Output isn't correct
15 Correct 6 ms 5240 KB Output is correct
16 Incorrect 5 ms 5284 KB Output isn't correct
17 Incorrect 7 ms 5240 KB Output isn't correct
18 Incorrect 7 ms 5240 KB Output isn't correct
19 Correct 7 ms 5240 KB Output is correct
20 Correct 7 ms 5240 KB Output is correct
21 Correct 6 ms 5240 KB Output is correct
22 Correct 7 ms 5240 KB Output is correct
23 Correct 7 ms 5240 KB Output is correct
24 Incorrect 7 ms 5240 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7160 KB Output is correct
2 Incorrect 49 ms 8056 KB Output isn't correct
3 Correct 39 ms 7288 KB Output is correct
4 Incorrect 48 ms 8184 KB Output isn't correct
5 Correct 35 ms 6980 KB Output is correct
6 Correct 38 ms 7288 KB Output is correct
7 Correct 43 ms 7540 KB Output is correct
8 Correct 43 ms 7544 KB Output is correct
9 Incorrect 56 ms 7952 KB Output isn't correct
10 Correct 191 ms 12292 KB Output is correct
11 Incorrect 79 ms 9464 KB Output isn't correct
12 Correct 116 ms 10616 KB Output is correct
13 Incorrect 92 ms 9852 KB Output isn't correct
14 Correct 77 ms 9052 KB Output is correct
15 Correct 124 ms 10660 KB Output is correct
16 Correct 128 ms 11084 KB Output is correct
17 Correct 99 ms 10364 KB Output is correct
18 Incorrect 105 ms 10468 KB Output isn't correct
19 Correct 135 ms 11640 KB Output is correct
20 Incorrect 245 ms 14588 KB Output isn't correct
21 Incorrect 270 ms 12724 KB Output isn't correct
22 Correct 175 ms 11784 KB Output is correct
23 Correct 178 ms 12792 KB Output is correct
24 Correct 173 ms 12580 KB Output is correct
25 Incorrect 167 ms 12292 KB Output isn't correct
26 Correct 141 ms 11804 KB Output is correct
27 Correct 169 ms 12772 KB Output is correct
28 Correct 193 ms 12792 KB Output is correct
29 Correct 190 ms 13176 KB Output is correct
30 Incorrect 277 ms 15132 KB Output isn't correct
31 Incorrect 204 ms 13944 KB Output isn't correct
32 Correct 186 ms 12664 KB Output is correct
33 Correct 202 ms 12920 KB Output is correct
34 Incorrect 206 ms 13304 KB Output isn't correct
35 Incorrect 169 ms 12944 KB Output isn't correct
36 Incorrect 171 ms 13384 KB Output isn't correct
37 Correct 238 ms 14464 KB Output is correct
38 Correct 209 ms 14200 KB Output is correct
39 Correct 248 ms 14172 KB Output is correct
40 Incorrect 275 ms 15716 KB Output isn't correct
41 Correct 357 ms 17780 KB Output is correct