oj.uz

Submission #155929

# Submission time Handle Problem Language Result Execution time Memory
155929 2019-10-02T05:36:37 Z Akashi 007 (CEOI14_007) C++14
0 / 100
 365 ms 18204 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 8 ms 5240 KB Output is correct
2 Correct 7 ms 5240 KB Output is correct
3 Correct 6 ms 5240 KB Output is correct
4 Incorrect 7 ms 5368 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 7 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 5216 KB Output is correct
11 Correct 7 ms 5284 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 5240 KB Output isn't correct
15 Correct 6 ms 5240 KB Output is correct
16 Incorrect 7 ms 5240 KB Output isn't correct
17 Incorrect 7 ms 5240 KB Output isn't correct
18 Incorrect 7 ms 5244 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 7 ms 5212 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 5368 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 7416 KB Output is correct
2 Incorrect 70 ms 8296 KB Output isn't correct
3 Correct 45 ms 7544 KB Output is correct
4 Incorrect 56 ms 8440 KB Output isn't correct
5 Correct 42 ms 7320 KB Output is correct
6 Correct 50 ms 7636 KB Output is correct
7 Correct 55 ms 7804 KB Output is correct
8 Correct 47 ms 7800 KB Output is correct
9 Incorrect 56 ms 8288 KB Output isn't correct
10 Correct 195 ms 12628 KB Output is correct
11 Incorrect 89 ms 9736 KB Output isn't correct
12 Correct 130 ms 10844 KB Output is correct
13 Incorrect 91 ms 10104 KB Output isn't correct
14 Correct 71 ms 9336 KB Output is correct
15 Correct 142 ms 10932 KB Output is correct
16 Correct 155 ms 11432 KB Output is correct
17 Correct 148 ms 10748 KB Output is correct
18 Incorrect 108 ms 10616 KB Output isn't correct
19 Correct 158 ms 11768 KB Output is correct
20 Incorrect 255 ms 14624 KB Output isn't correct
21 Incorrect 190 ms 12964 KB Output isn't correct
22 Correct 153 ms 12024 KB Output is correct
23 Correct 186 ms 12920 KB Output is correct
24 Correct 186 ms 12768 KB Output is correct
25 Incorrect 185 ms 12420 KB Output isn't correct
26 Correct 163 ms 12024 KB Output is correct
27 Correct 191 ms 13048 KB Output is correct
28 Correct 202 ms 13084 KB Output is correct
29 Correct 193 ms 13412 KB Output is correct
30 Incorrect 283 ms 15484 KB Output isn't correct
31 Incorrect 213 ms 14200 KB Output isn't correct
32 Correct 196 ms 13020 KB Output is correct
33 Correct 183 ms 13176 KB Output is correct
34 Incorrect 211 ms 13560 KB Output isn't correct
35 Incorrect 170 ms 13308 KB Output isn't correct
36 Incorrect 197 ms 13548 KB Output isn't correct
37 Correct 227 ms 14560 KB Output is correct
38 Correct 233 ms 14456 KB Output is correct
39 Correct 262 ms 14428 KB Output is correct
40 Incorrect 271 ms 15992 KB Output isn't correct
41 Correct 365 ms 18204 KB Output is correct