oj.uz

Submission #155931

# Submission time Handle Problem Language Result Execution time Memory
155931 2019-10-02T05:40:11 Z Akashi 007 (CEOI14_007) C++14
0 / 100
 373 ms 17960 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, ds[i]);

        for(int i = 1; i <= n ; ++i)
            if(da[i] == db[i] && da[i] + dd[i] == ds[a]) nr2 = max(nr2, dd[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 7 ms 5240 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Partially correct 6 ms 5240 KB Partially correct
4 Incorrect 7 ms 5240 KB Output isn't correct
5 Incorrect 7 ms 5240 KB Output isn't correct
6 Correct 7 ms 5240 KB Output is correct
7 Correct 5 ms 5240 KB Output is correct
8 Incorrect 7 ms 5240 KB Output isn't correct
9 Correct 9 ms 5304 KB Output is correct
10 Correct 6 ms 5240 KB Output is correct
11 Correct 8 ms 5240 KB Output is correct
12 Incorrect 8 ms 5240 KB Output isn't correct
13 Correct 7 ms 5240 KB Output is correct
14 Incorrect 7 ms 5180 KB Output isn't correct
15 Correct 7 ms 5240 KB Output is correct
16 Incorrect 8 ms 5236 KB Output isn't correct
17 Incorrect 8 ms 5240 KB Output isn't correct
18 Incorrect 8 ms 5240 KB Output isn't correct
19 Correct 9 ms 5240 KB Output is correct
20 Correct 8 ms 5240 KB Output is correct
21 Correct 8 ms 5240 KB Output is correct
22 Correct 8 ms 5240 KB Output is correct
23 Correct 8 ms 5240 KB Output is correct
24 Incorrect 8 ms 5368 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7248 KB Output is correct
2 Incorrect 48 ms 8184 KB Output isn't correct
3 Correct 45 ms 7416 KB Output is correct
4 Incorrect 69 ms 8312 KB Output isn't correct
5 Correct 38 ms 7108 KB Output is correct
6 Correct 46 ms 7416 KB Output is correct
7 Correct 54 ms 7672 KB Output is correct
8 Correct 55 ms 7616 KB Output is correct
9 Incorrect 64 ms 8056 KB Output isn't correct
10 Correct 228 ms 12664 KB Output is correct
11 Incorrect 150 ms 9720 KB Output isn't correct
12 Correct 172 ms 10664 KB Output is correct
13 Incorrect 139 ms 9888 KB Output isn't correct
14 Correct 74 ms 9208 KB Output is correct
15 Correct 119 ms 10920 KB Output is correct
16 Correct 146 ms 10968 KB Output is correct
17 Correct 112 ms 10436 KB Output is correct
18 Incorrect 113 ms 10604 KB Output isn't correct
19 Correct 162 ms 11640 KB Output is correct
20 Incorrect 301 ms 14556 KB Output isn't correct
21 Incorrect 216 ms 12912 KB Output isn't correct
22 Correct 152 ms 11876 KB Output is correct
23 Correct 184 ms 12908 KB Output is correct
24 Correct 193 ms 12728 KB Output is correct
25 Incorrect 160 ms 12332 KB Output isn't correct
26 Correct 161 ms 11900 KB Output is correct
27 Correct 192 ms 12920 KB Output is correct
28 Correct 209 ms 13020 KB Output is correct
29 Correct 195 ms 13276 KB Output is correct
30 Incorrect 335 ms 15376 KB Output isn't correct
31 Incorrect 223 ms 14104 KB Output isn't correct
32 Correct 206 ms 12772 KB Output is correct
33 Correct 221 ms 13164 KB Output is correct
34 Incorrect 274 ms 13452 KB Output isn't correct
35 Incorrect 195 ms 13176 KB Output isn't correct
36 Incorrect 239 ms 13528 KB Output isn't correct
37 Correct 231 ms 14584 KB Output is correct
38 Correct 220 ms 14328 KB Output is correct
39 Correct 258 ms 14320 KB Output is correct
40 Incorrect 279 ms 15816 KB Output isn't correct
41 Correct 373 ms 17960 KB Output is correct