oj.uz

Submission #490313

# Submission time Handle Problem Language Result Execution time Memory
490313 2021-11-27T00:36:34 Z SirCovidThe19th 007 (CEOI14_007) C++17
30 / 100
 429 ms 16208 KB 
#include <bits/stdc++.h>
using namespace std;

const int mx = 2e5 + 5;

int n, m, s, v, a, b, dA[mx], dB[mx], ans; vector<int> adj[mx];

void bfs(int st, int *D){
    queue<int> Q; fill(D, D + n + 1, -1); 
    Q.push(st); D[st] = 0;
    while (!Q.empty()){
        int i = Q.front(); Q.pop();
        for (int j : adj[i]) if (D[j] == -1) D[j] = D[i] + 1, Q.push(j);
    }
}
int same(int pos){
    int d = 0;
    while (1){
        bool ok = 0;
        for (int i : adj[pos]) if (dA[i] < dA[pos] and dB[i] < dB[pos]){
            pos = i; ok = 1; d++; 
            break;
        }
        if (!ok) break;
    }
    return d;
}

int main(){
    cin >> n >> m >> s >> v >> a >> b;
    for (int i = 1; i <= m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    bfs(a, dA); bfs(b, dB);
    int wA = dA[v] - dA[s], wB = dB[v] - dB[s];

    if (wA == wB) ans = (same(s) < same(v) ? wA - 1 : wA);
    else ans = min(wA, wB);

    cout<<max(ans, -1)<<endl;
}

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Partially correct 2 ms 4992 KB Partially correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4988 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Partially correct 2 ms 4940 KB Partially correct
7 Partially correct 2 ms 4940 KB Partially correct
8 Correct 2 ms 4944 KB Output is correct
9 Partially correct 2 ms 4940 KB Partially correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Partially correct 3 ms 4940 KB Partially correct
14 Correct 2 ms 4940 KB Output is correct
15 Partially correct 3 ms 4940 KB Partially correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Partially correct 3 ms 4940 KB Partially correct
20 Partially correct 3 ms 4940 KB Partially correct
21 Correct 4 ms 4940 KB Output is correct
22 Partially correct 3 ms 4940 KB Partially correct
23 Partially correct 3 ms 4940 KB Partially correct
24 Correct 3 ms 4940 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 31 ms 6560 KB Partially correct
2 Correct 42 ms 7228 KB Output is correct
3 Partially correct 33 ms 6632 KB Partially correct
4 Correct 43 ms 7360 KB Output is correct
5 Correct 33 ms 6444 KB Output is correct
6 Correct 33 ms 6724 KB Output is correct
7 Partially correct 43 ms 6840 KB Partially correct
8 Correct 35 ms 6784 KB Output is correct
9 Correct 57 ms 7292 KB Output is correct
10 Partially correct 250 ms 11604 KB Partially correct
11 Correct 67 ms 8512 KB Output is correct
12 Partially correct 93 ms 9320 KB Partially correct
13 Correct 83 ms 8792 KB Output is correct
14 Correct 83 ms 8124 KB Output is correct
15 Partially correct 91 ms 9412 KB Partially correct
16 Correct 105 ms 9656 KB Output is correct
17 Correct 98 ms 9228 KB Output is correct
18 Correct 104 ms 9152 KB Output is correct
19 Partially correct 162 ms 10436 KB Partially correct
20 Correct 284 ms 13268 KB Output is correct
21 Correct 123 ms 11200 KB Output is correct
22 Partially correct 118 ms 10340 KB Partially correct
23 Partially correct 123 ms 11132 KB Partially correct
24 Partially correct 119 ms 11032 KB Partially correct
25 Correct 118 ms 10792 KB Output is correct
26 Partially correct 108 ms 10444 KB Partially correct
27 Correct 137 ms 11204 KB Output is correct
28 Correct 134 ms 11204 KB Output is correct
29 Partially correct 187 ms 11844 KB Partially correct
30 Correct 309 ms 13764 KB Output is correct
31 Correct 148 ms 12100 KB Output is correct
32 Partially correct 132 ms 11136 KB Partially correct
33 Partially correct 130 ms 11292 KB Partially correct
34 Correct 142 ms 11636 KB Output is correct
35 Correct 141 ms 11460 KB Output is correct
36 Correct 170 ms 11644 KB Output is correct
37 Correct 156 ms 12600 KB Output is correct
38 Correct 158 ms 12416 KB Output is correct
39 Correct 172 ms 12568 KB Output is correct
40 Correct 255 ms 13892 KB Output is correct
41 Partially correct 429 ms 16208 KB Partially correct