oj.uz

Submission #257833

# Submission time Handle Problem Language Result Execution time Memory
257833 2020-08-04T22:14:03 Z doowey 007 (CEOI14_007) C++14
30 / 100
 337 ms 18552 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];
    cout << max(-1,min(d0,d1)-1);
    return 0;
}

Subtask #1
9.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 4992 KB Partially correct
2 Partially correct 3 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 4 ms 4992 KB Output is correct
6 Partially correct 4 ms 4992 KB Partially correct
7 Partially correct 3 ms 4992 KB Partially correct
8 Correct 3 ms 4992 KB Output is correct
9 Partially correct 4 ms 4992 KB Partially correct
10 Partially correct 3 ms 4992 KB Partially correct
11 Partially correct 3 ms 4992 KB Partially correct
12 Correct 3 ms 5120 KB Output is correct
13 Partially correct 3 ms 5120 KB Partially correct
14 Correct 4 ms 5120 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 Partially correct 3 ms 5120 KB Partially correct
22 Partially correct 4 ms 5120 KB Partially correct
23 Partially correct 4 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 26 ms 7424 KB Partially correct
2 Correct 35 ms 8568 KB Output is correct
3 Partially correct 31 ms 7552 KB Partially correct
4 Correct 35 ms 8696 KB Output is correct
5 Partially correct 27 ms 7368 KB Partially correct
6 Partially correct 33 ms 7680 KB Partially correct
7 Partially correct 32 ms 7928 KB Partially correct
8 Partially correct 30 ms 7928 KB Partially correct
9 Correct 43 ms 8824 KB Output is correct
10 Partially correct 159 ms 13252 KB Partially correct
11 Correct 70 ms 10364 KB Output is correct
12 Partially correct 102 ms 11384 KB Partially correct
13 Correct 66 ms 10744 KB Output is correct
14 Correct 62 ms 9848 KB Output is correct
15 Partially correct 80 ms 11512 KB Partially correct
16 Partially correct 97 ms 11904 KB Partially correct
17 Partially correct 88 ms 11256 KB Partially correct
18 Correct 102 ms 11256 KB Output is correct
19 Partially correct 138 ms 12408 KB Partially correct
20 Correct 238 ms 15252 KB Output is correct
21 Correct 152 ms 13688 KB Output is correct
22 Partially correct 117 ms 12644 KB Partially correct
23 Partially correct 118 ms 13520 KB Partially correct
24 Partially correct 118 ms 13432 KB Partially correct
25 Correct 112 ms 13048 KB Output is correct
26 Partially correct 128 ms 12780 KB Partially correct
27 Partially correct 126 ms 13676 KB Partially correct
28 Partially correct 138 ms 13688 KB Partially correct
29 Partially correct 153 ms 14072 KB Partially correct
30 Correct 231 ms 15964 KB Output is correct
31 Correct 145 ms 14684 KB Output is correct
32 Partially correct 182 ms 13560 KB Partially correct
33 Partially correct 124 ms 13816 KB Partially correct
34 Correct 186 ms 14072 KB Output is correct
35 Correct 115 ms 13816 KB Output is correct
36 Correct 138 ms 14200 KB Output is correct
37 Partially correct 157 ms 15144 KB Partially correct
38 Partially correct 169 ms 14968 KB Partially correct
39 Partially correct 182 ms 15004 KB Partially correct
40 Correct 259 ms 16504 KB Output is correct
41 Partially correct 337 ms 18552 KB Partially correct