oj.uz

Submission #257834

# Submission time Handle Problem Language Result Execution time Memory
257834 2020-08-04T22:15:34 Z doowey 007 (CEOI14_007) C++14
30 / 100
 330 ms 17788 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){
        int low = min(d0,d1);
        if(low < 0) cout << -1 << "\n";
        else cout << low << "\n";
        return 0;
    }
    cout << max(-1,min(d0,d1)-1);
    return 0;
}

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Partially correct 4 ms 4992 KB Partially correct
3 Partially correct 3 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 4992 KB Partially correct
7 Partially correct 3 ms 4992 KB Partially correct
8 Correct 4 ms 4992 KB Output is correct
9 Partially correct 3 ms 4992 KB Partially correct
10 Correct 4 ms 4992 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 4 ms 5120 KB Output is correct
13 Partially correct 3 ms 5120 KB Partially correct
14 Correct 4 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 3 ms 5120 KB Partially correct
20 Partially correct 4 ms 5120 KB Partially correct
21 Correct 3 ms 5120 KB Output is correct
22 Partially correct 3 ms 5120 KB Partially correct
23 Partially correct 3 ms 5120 KB Partially correct
24 Correct 4 ms 5120 KB Output is correct

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 27 ms 6904 KB Partially correct
2 Correct 34 ms 7800 KB Output is correct
3 Partially correct 27 ms 7040 KB Partially correct
4 Correct 38 ms 7928 KB Output is correct
5 Correct 25 ms 6904 KB Output is correct
6 Correct 29 ms 7168 KB Output is correct
7 Partially correct 29 ms 7296 KB Partially correct
8 Partially correct 31 ms 7296 KB Partially correct
9 Correct 45 ms 7800 KB Output is correct
10 Partially correct 153 ms 12284 KB Partially correct
11 Correct 58 ms 9336 KB Output is correct
12 Partially correct 105 ms 10488 KB Partially correct
13 Correct 69 ms 9804 KB Output is correct
14 Correct 51 ms 8952 KB Output is correct
15 Partially correct 75 ms 10616 KB Partially correct
16 Correct 100 ms 10908 KB Output is correct
17 Partially correct 93 ms 10360 KB Partially correct
18 Correct 81 ms 10360 KB Output is correct
19 Partially correct 116 ms 11512 KB Partially correct
20 Correct 231 ms 14328 KB Output is correct
21 Correct 143 ms 12796 KB Output is correct
22 Partially correct 125 ms 11640 KB Partially correct
23 Partially correct 127 ms 12664 KB Partially correct
24 Partially correct 121 ms 12664 KB Partially correct
25 Correct 134 ms 12280 KB Output is correct
26 Partially correct 119 ms 11768 KB Partially correct
27 Partially correct 138 ms 12792 KB Partially correct
28 Partially correct 169 ms 12792 KB Partially correct
29 Partially correct 178 ms 13176 KB Partially correct
30 Correct 261 ms 15096 KB Output is correct
31 Correct 160 ms 13944 KB Output is correct
32 Partially correct 136 ms 12536 KB Partially correct
33 Partially correct 134 ms 12932 KB Partially correct
34 Correct 140 ms 13176 KB Output is correct
35 Correct 123 ms 12924 KB Output is correct
36 Correct 121 ms 13300 KB Output is correct
37 Correct 164 ms 14288 KB Output is correct
38 Partially correct 182 ms 14072 KB Partially correct
39 Partially correct 189 ms 14104 KB Partially correct
40 Correct 247 ms 15740 KB Output is correct
41 Partially correct 330 ms 17788 KB Partially correct