oj.uz

Submission #82363

# Submission time Handle Problem Language Result Execution time Memory
82363 2018-10-30T09:49:46 Z FutymyClone 007 (CEOI14_007) C++14
0 / 100
 413 ms 87572 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, m, s, d, a, b, dist[2][N];
vector <int> g[N];
queue <int> q;

void bfs (int type){
    if (!type) memset(dist, 0x3f, sizeof(dist));
    dist[type][(type == 0) ? d : s] = 0;
    q.push((type == 0) ? d : s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v: g[u]) {
            if (type == 0 && v == s) continue;
            if (dist[type][v] > dist[type][u] + 1) {
                dist[type][v] = dist[type][u] + 1;
                q.push(v);
            }
        }
    }
}

int main(){
    #ifdef Futymy
        freopen("SPY.inp", "r", stdin);
        freopen("SPY.out", "w", stdout);
    #endif // Futymy
    scanf("%d %d", &n, &m);
    scanf("%d %d %d %d", &s, &d, &a, &b);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v); g[v].push_back(u);
    }

    bfs(0); bfs(1);
    //for (int i = 1; i <= n; i++) cout << dist[0][i] << " ";
    //cout << "\n";
    int Min = min(dist[0][a], dist[0][b]);
    //cout << dist[0][a] << " " << dist[0][b] << "\n";
    if (Min > 1e9) printf("%d", dist[1][d]);
    else {
        if (dist[0][a] < 1e9 && dist[0][b] > 1e9) {
            if (dist[1][a] > dist[0][a]) printf("%d", -1);
            else printf("%d", min(dist[1][d], dist[0][a] - dist[1][a]));
        }
        else if (dist[0][a] > 1e9 && dist[0][b] < 1e9) {
            if (dist[1][b] > dist[0][b]) printf("%d", -1);
            else printf("%d", min(dist[1][d], dist[0][b] - dist[1][b]));
        }
        else {
            if (dist[1][b] > dist[0][b] || dist[1][a] > dist[0][a]) printf("%d", -1);
            else printf("%d", min(dist[0][a] - dist[1][a], dist[0][b] - dist[1][b]));
        }
    }
    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:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6520 KB Output is correct
2 Correct 10 ms 6520 KB Output is correct
3 Correct 8 ms 6664 KB Output is correct
4 Incorrect 7 ms 6684 KB Output isn't correct
5 Incorrect 8 ms 6684 KB Output isn't correct
6 Correct 8 ms 6740 KB Output is correct
7 Correct 9 ms 6756 KB Output is correct
8 Incorrect 7 ms 6756 KB Output isn't correct
9 Correct 8 ms 6756 KB Output is correct
10 Correct 7 ms 6756 KB Output is correct
11 Correct 8 ms 6816 KB Output is correct
12 Incorrect 7 ms 6816 KB Output isn't correct
13 Correct 10 ms 6816 KB Output is correct
14 Incorrect 8 ms 6836 KB Output isn't correct
15 Correct 14 ms 6836 KB Output is correct
16 Incorrect 9 ms 6836 KB Output isn't correct
17 Incorrect 8 ms 6836 KB Output isn't correct
18 Incorrect 10 ms 6880 KB Output isn't correct
19 Correct 8 ms 6880 KB Output is correct
20 Correct 7 ms 6880 KB Output is correct
21 Correct 8 ms 6880 KB Output is correct
22 Correct 8 ms 6880 KB Output is correct
23 Incorrect 7 ms 6880 KB Output isn't correct
24 Incorrect 8 ms 6880 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 8032 KB Output is correct
2 Incorrect 37 ms 8684 KB Output isn't correct
3 Correct 30 ms 8684 KB Output is correct
4 Incorrect 41 ms 8684 KB Output isn't correct
5 Correct 30 ms 8684 KB Output is correct
6 Correct 30 ms 8684 KB Output is correct
7 Correct 36 ms 8684 KB Output is correct
8 Correct 34 ms 8684 KB Output is correct
9 Incorrect 51 ms 8760 KB Output isn't correct
10 Correct 245 ms 12988 KB Output is correct
11 Incorrect 105 ms 12988 KB Output isn't correct
12 Correct 81 ms 12988 KB Output is correct
13 Incorrect 107 ms 12988 KB Output isn't correct
14 Correct 53 ms 12988 KB Output is correct
15 Correct 91 ms 13404 KB Output is correct
16 Correct 79 ms 15020 KB Output is correct
17 Correct 66 ms 15840 KB Output is correct
18 Incorrect 84 ms 17196 KB Output isn't correct
19 Correct 138 ms 20792 KB Output is correct
20 Incorrect 253 ms 29244 KB Output isn't correct
21 Incorrect 111 ms 29244 KB Output isn't correct
22 Correct 107 ms 29800 KB Output is correct
23 Correct 115 ms 32404 KB Output is correct
24 Correct 113 ms 34376 KB Output is correct
25 Incorrect 109 ms 35760 KB Output isn't correct
26 Correct 96 ms 37296 KB Output is correct
27 Correct 109 ms 39812 KB Output is correct
28 Correct 133 ms 41860 KB Output is correct
29 Correct 170 ms 46052 KB Output is correct
30 Incorrect 263 ms 53740 KB Output isn't correct
31 Incorrect 167 ms 53940 KB Output isn't correct
32 Correct 121 ms 55172 KB Output is correct
33 Correct 130 ms 57460 KB Output is correct
34 Incorrect 171 ms 59908 KB Output isn't correct
35 Incorrect 127 ms 61728 KB Output isn't correct
36 Incorrect 159 ms 64120 KB Output isn't correct
37 Correct 169 ms 67284 KB Output is correct
38 Correct 162 ms 69500 KB Output is correct
39 Correct 183 ms 71888 KB Output is correct
40 Incorrect 257 ms 77996 KB Output isn't correct
41 Correct 413 ms 87572 KB Output is correct