oj.uz

Submission #95410

# Submission time Handle Problem Language Result Execution time Memory
95410 2019-01-31T18:43:16 Z popovicirobert 007 (CEOI14_007) C++14
0 / 100
 294 ms 16540 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = (int) 2e5;

vector <int> g[MAXN + 1];
int dst[MAXN + 1][2];

inline void bfs(int nod, bool t) {
    queue <int> Q;
    dst[nod][t] = 1;
    Q.push(nod);
    while(Q.size()) {
        nod = Q.front();
        Q.pop();
        for(auto it : g[nod]) {
            if(dst[it][t] == 0) {
                dst[it][t] = dst[nod][t] + 1;
                Q.push(it);
            }
        }
    }
}

int dfs(int nod) {
    for(auto it : g[nod]) {
        if(dst[nod][0] == dst[it][0] + 1 && dst[nod][1] == dst[it][1] + 1) {
            return dfs(it) + 1;
        }
    }
    return 0;
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m, s, d, a, b;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    cin >> s >> d >> a >> b;
    for(i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs(a, 0);
    bfs(b, 1);
    if(dst[s][0] != dst[d][0] || dst[s][1] != dst[d][1]) {
        cout << max(-1, min(dst[d][0] - dst[s][0], dst[d][1] - dst[s][1]));
        return 0;
    }
    int cnt_s = dfs(s), cnt_d = dfs(d);
    int ans = -1;
    if(dst[s][0] <= dst[d][0]) {
        if(cnt_s + dst[d][0] - dst[s][0] >= cnt_d) {
            ans = max(ans, dst[d][0] - dst[s][0]);
        }
        else {
            ans = max(ans, dst[d][0] - dst[s][0] - 1);
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 5 ms 4984 KB Output is correct
3 Correct 6 ms 4988 KB Output is correct
4 Incorrect 5 ms 4984 KB Output isn't correct
5 Incorrect 6 ms 4984 KB Output isn't correct
6 Correct 6 ms 5112 KB Output is correct
7 Correct 6 ms 4984 KB Output is correct
8 Incorrect 5 ms 4984 KB Output isn't correct
9 Correct 5 ms 4984 KB Output is correct
10 Correct 5 ms 5112 KB Output is correct
11 Correct 5 ms 5156 KB Output is correct
12 Incorrect 5 ms 5212 KB Output isn't correct
13 Correct 5 ms 5112 KB Output is correct
14 Incorrect 5 ms 5004 KB Output isn't correct
15 Correct 5 ms 4984 KB Output is correct
16 Incorrect 5 ms 5092 KB Output isn't correct
17 Incorrect 5 ms 5112 KB Output isn't correct
18 Incorrect 5 ms 5112 KB Output isn't correct
19 Correct 5 ms 5112 KB Output is correct
20 Correct 5 ms 5112 KB Output is correct
21 Correct 5 ms 4984 KB Output is correct
22 Correct 5 ms 5116 KB Output is correct
23 Correct 5 ms 5112 KB Output is correct
24 Incorrect 5 ms 5128 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6924 KB Output is correct
2 Incorrect 26 ms 7544 KB Output isn't correct
3 Correct 22 ms 6904 KB Output is correct
4 Incorrect 31 ms 7672 KB Output isn't correct
5 Correct 26 ms 6776 KB Output is correct
6 Correct 27 ms 7032 KB Output is correct
7 Correct 26 ms 7252 KB Output is correct
8 Correct 29 ms 7160 KB Output is correct
9 Incorrect 43 ms 7672 KB Output isn't correct
10 Correct 145 ms 11960 KB Output is correct
11 Incorrect 43 ms 8872 KB Output isn't correct
12 Correct 59 ms 9768 KB Output is correct
13 Incorrect 45 ms 9080 KB Output isn't correct
14 Correct 38 ms 8440 KB Output is correct
15 Correct 52 ms 9848 KB Output is correct
16 Correct 54 ms 10104 KB Output is correct
17 Correct 58 ms 9592 KB Output is correct
18 Incorrect 61 ms 9624 KB Output isn't correct
19 Correct 107 ms 10744 KB Output is correct
20 Incorrect 190 ms 13560 KB Output isn't correct
21 Incorrect 85 ms 11620 KB Output isn't correct
22 Correct 86 ms 10764 KB Output is correct
23 Correct 79 ms 11512 KB Output is correct
24 Correct 98 ms 11388 KB Output is correct
25 Incorrect 101 ms 11128 KB Output isn't correct
26 Correct 80 ms 10744 KB Output is correct
27 Correct 109 ms 11512 KB Output is correct
28 Correct 132 ms 11704 KB Output is correct
29 Correct 145 ms 12256 KB Output is correct
30 Incorrect 220 ms 14216 KB Output isn't correct
31 Incorrect 129 ms 12536 KB Output isn't correct
32 Correct 135 ms 11548 KB Output is correct
33 Correct 96 ms 11688 KB Output is correct
34 Incorrect 152 ms 12124 KB Output isn't correct
35 Incorrect 115 ms 11740 KB Output isn't correct
36 Incorrect 106 ms 12024 KB Output isn't correct
37 Correct 138 ms 12908 KB Output is correct
38 Correct 145 ms 12664 KB Output is correct
39 Correct 170 ms 12792 KB Output is correct
40 Incorrect 213 ms 14456 KB Output isn't correct
41 Correct 294 ms 16540 KB Output is correct