oj.uz

Submission #82418

# Submission time Handle Problem Language Result Execution time Memory
82418 2018-10-30T13:53:38 Z Flying_dragon_02 007 (CEOI14_007) C++14
0 / 100
 363 ms 16568 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 2e5 + 5;

int n, m, s, d, a, b, dist[2][N];

const int inf = 1e8;

vector<int> graph[N];

queue<ii> pq;

int main() {
    //freopen("spy.inp", "r", stdin);
    //freopen("spy.out", "w", stdout);
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &s, &d, &a, &b);
    for(int i = 1; i <= n; i++)
        dist[0][i] = dist[1][i] = inf;
    for(int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        graph[u].pb(v);
        graph[v].pb(u);
    }
    dist[0][s] = 0;
    pq.push({dist[0][s], s});
    while(!pq.empty()) {
        ii frt = pq.front();
        pq.pop();
        int u = frt.se;
        if(frt.fi > dist[0][u]) continue;
        for(int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            if(dist[0][u] + 1 < dist[0][v]) {
                dist[0][v] = dist[0][u] + 1;
                pq.push({dist[0][v], v});
            }
        }
    }
    dist[1][d] = 0;
    pq.push({dist[1][d], d});
    while(!pq.empty()) {
        ii frt = pq.front();
        pq.pop();
        int u = frt.se;
        if(frt.fi > dist[1][u]) continue;
        for(int i = 0; i < graph[u].size(); i++) {
            int v = graph[u][i];
            if(dist[1][u] + 1 < dist[1][v]) {
                dist[1][v] = dist[1][u] + 1;
                pq.push({dist[1][v], v});
            }
        }
    }
    if(dist[1][a] >= dist[0][a] && dist[1][b] >= dist[0][b])
        printf("%d", min(dist[1][a] - dist[0][a], dist[1][b] - dist[0][b]));
    else
        printf("-1");
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:42:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < graph[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~~
007.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < graph[u].size(); i++) {
                        ~~^~~~~~~~~~~~~~~~~
007.cpp:25: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:26: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:31: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 6 ms 4988 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5176 KB Output is correct
4 Incorrect 6 ms 5244 KB Output isn't correct
5 Incorrect 6 ms 5244 KB Output isn't correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 6 ms 5244 KB Output is correct
8 Incorrect 5 ms 5244 KB Output isn't correct
9 Correct 6 ms 5280 KB Output is correct
10 Correct 6 ms 5324 KB Output is correct
11 Correct 6 ms 5324 KB Output is correct
12 Incorrect 6 ms 5324 KB Output isn't correct
13 Correct 6 ms 5324 KB Output is correct
14 Incorrect 6 ms 5324 KB Output isn't correct
15 Correct 6 ms 5356 KB Output is correct
16 Incorrect 6 ms 5356 KB Output isn't correct
17 Incorrect 6 ms 5356 KB Output isn't correct
18 Incorrect 6 ms 5356 KB Output isn't correct
19 Correct 6 ms 5356 KB Output is correct
20 Correct 8 ms 5356 KB Output is correct
21 Correct 6 ms 5356 KB Output is correct
22 Correct 6 ms 5356 KB Output is correct
23 Correct 6 ms 5356 KB Output is correct
24 Incorrect 6 ms 5356 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6908 KB Output is correct
2 Incorrect 41 ms 7572 KB Output isn't correct
3 Correct 31 ms 7572 KB Output is correct
4 Incorrect 41 ms 7676 KB Output isn't correct
5 Correct 35 ms 7676 KB Output is correct
6 Correct 34 ms 7676 KB Output is correct
7 Correct 35 ms 7676 KB Output is correct
8 Correct 35 ms 7676 KB Output is correct
9 Incorrect 53 ms 7676 KB Output isn't correct
10 Correct 197 ms 11900 KB Output is correct
11 Incorrect 63 ms 11900 KB Output isn't correct
12 Correct 85 ms 11900 KB Output is correct
13 Incorrect 68 ms 11900 KB Output isn't correct
14 Correct 56 ms 11900 KB Output is correct
15 Correct 76 ms 11900 KB Output is correct
16 Correct 88 ms 11900 KB Output is correct
17 Correct 105 ms 11900 KB Output is correct
18 Incorrect 77 ms 11900 KB Output isn't correct
19 Correct 130 ms 11900 KB Output is correct
20 Incorrect 233 ms 13692 KB Output isn't correct
21 Incorrect 110 ms 13692 KB Output isn't correct
22 Correct 105 ms 13692 KB Output is correct
23 Correct 118 ms 13692 KB Output is correct
24 Correct 111 ms 13692 KB Output is correct
25 Incorrect 105 ms 13692 KB Output isn't correct
26 Correct 99 ms 13692 KB Output is correct
27 Correct 130 ms 13692 KB Output is correct
28 Correct 127 ms 13692 KB Output is correct
29 Correct 171 ms 13692 KB Output is correct
30 Incorrect 264 ms 14148 KB Output isn't correct
31 Incorrect 131 ms 14148 KB Output isn't correct
32 Correct 122 ms 14148 KB Output is correct
33 Correct 115 ms 14148 KB Output is correct
34 Incorrect 144 ms 14148 KB Output isn't correct
35 Incorrect 121 ms 14148 KB Output isn't correct
36 Incorrect 131 ms 14148 KB Output isn't correct
37 Correct 146 ms 14148 KB Output is correct
38 Correct 145 ms 14148 KB Output is correct
39 Correct 170 ms 14148 KB Output is correct
40 Incorrect 219 ms 14288 KB Output isn't correct
41 Correct 363 ms 16568 KB Output is correct