oj.uz

Submission #257826

# Submission time Handle Problem Language Result Execution time Memory
257826 2020-08-04T22:04:36 Z doowey 007 (CEOI14_007) C++14
27 / 100
 343 ms 18040 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
vector<int> T[N];

int c = 0;
int d[4][N];
int n;

void bfs(int node){
    for(int i = 1; i <= n; i ++ )
        d[c][i] = (int)1e9;
    queue<int> bf;
    bf.push(node);
    d[c][node] = 0;
    while(!bf.empty()){
        node = bf.front();
        bf.pop();
        for(auto x : T[node]){
            if(d[c][x] > d[c][node] + 1){
                d[c][x] = d[c][node] + 1;
                bf.push(x);
            }
        }
    }
    c ++ ;
}

int main(){
    fastIO;
    int m;
    cin >> n >> m;
    int a, b;
    cin >> a >> b;
    int n0, n1;
    cin >> n0 >> n1;
    int u, v;
    for(int i = 0 ; i < m ; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    bfs(a);
    bfs(b);
    bfs(n0);
    bfs(n1);
    int d0 = d[1][n0] - d[0][n0];
    int d1 = d[1][n1] - d[0][n1];
    if(d0 == d1 + 1){
        cout << max(-1,d1) << "\n";
    }
    else if(d1 == d0 + 1){
        cout << max(-1,d0) << "\n";
    }
    else{
        int cc = 0;
        int dd = 0;
        for(int i = 1; i <= n; i ++ ){
            if(d[0][i] + d[3][i] == d[0][n0] && d[0][i] + d[4][i] == d[0][n1]){
                cc = max(cc, d[0][i]);
            }
            if(d[1][i] + d[3][i] == d[1][n0] && d[1][i] + d[4][i] == d[1][n1]){
                dd = max(dd, d[1][i]);
            }
        }
        cout << max(-1,d0-1) << "\n";
    }
    return 0;
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:69:62: warning: array subscript is above array bounds [-Warray-bounds]
             if(d[0][i] + d[3][i] == d[0][n0] && d[0][i] + d[4][i] == d[0][n1]){
                                                           ~~~^
007.cpp:72:62: warning: array subscript is above array bounds [-Warray-bounds]
             if(d[1][i] + d[3][i] == d[1][n0] && d[1][i] + d[4][i] == d[1][n1]){
                                                           ~~~^

Subtask #1
6.0 / 30.0

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

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 33 ms 7288 KB Partially correct
2 Correct 39 ms 8184 KB Output is correct
3 Partially correct 27 ms 7416 KB Partially correct
4 Correct 36 ms 8320 KB Output is correct
5 Partially correct 25 ms 7296 KB Partially correct
6 Partially correct 28 ms 7552 KB Partially correct
7 Partially correct 30 ms 7672 KB Partially correct
8 Partially correct 30 ms 7672 KB Partially correct
9 Correct 44 ms 8184 KB Output is correct
10 Partially correct 155 ms 12536 KB Partially correct
11 Correct 58 ms 9720 KB Output is correct
12 Partially correct 89 ms 10744 KB Partially correct
13 Correct 67 ms 9976 KB Output is correct
14 Correct 64 ms 9336 KB Output is correct
15 Partially correct 77 ms 10872 KB Partially correct
16 Partially correct 83 ms 11256 KB Partially correct
17 Partially correct 75 ms 10488 KB Partially correct
18 Correct 88 ms 10616 KB Output is correct
19 Partially correct 122 ms 11768 KB Partially correct
20 Correct 247 ms 14584 KB Output is correct
21 Correct 139 ms 13048 KB Output is correct
22 Partially correct 116 ms 12024 KB Partially correct
23 Partially correct 123 ms 12920 KB Partially correct
24 Partially correct 117 ms 12792 KB Partially correct
25 Correct 136 ms 12536 KB Output is correct
26 Partially correct 125 ms 12024 KB Partially correct
27 Partially correct 155 ms 12920 KB Partially correct
28 Partially correct 168 ms 12904 KB Partially correct
29 Partially correct 156 ms 13432 KB Partially correct
30 Correct 226 ms 15352 KB Output is correct
31 Correct 151 ms 14072 KB Output is correct
32 Partially correct 145 ms 12972 KB Partially correct
33 Partially correct 124 ms 13176 KB Partially correct
34 Correct 147 ms 13476 KB Output is correct
35 Correct 149 ms 13180 KB Output is correct
36 Correct 128 ms 13636 KB Output is correct
37 Partially correct 193 ms 14584 KB Partially correct
38 Partially correct 204 ms 14328 KB Partially correct
39 Partially correct 235 ms 14328 KB Partially correct
40 Correct 257 ms 15864 KB Output is correct
41 Partially correct 343 ms 18040 KB Partially correct