oj.uz

Submission #391819

# Submission time Handle Problem Language Result Execution time Memory
391819 2021-04-20T03:18:48 Z abc864197532 007 (CEOI14_007) C++17
0 / 100
 266 ms 21320 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define pii pair<int,int>
#define pll pair<lli,lli>
#define X first
#define Y second
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
    for (auto a : x) cout << a << endl; \
    cout << endl;\
}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 300000, abc = 864197532, Doludu = 123;

vector <int> adj[N];
int dist[N], disa[N], disb[N], s, t, a, b, n;

bool chk(int d) {
    int mna = 1 << 30, mnb = 1 << 30;
    for (int i = 0; i < n; ++i) if (dist[i] <= d) mna = min(mna, disa[i]), mnb = min(mnb, disb[i]);
    if (mna < disa[s]) return false;
    if (mnb < disb[s]) return false;
    return true;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int m;
    cin >> n >> m >> s >> t >> a >> b, --s, --t, --a, --b;
    for (int i = 0, u, v; i < m; ++i) {
        cin >> u >> v, --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i = 0; i < n; ++i) dist[i] = -1;
    dist[t] = 0;
    queue <int> q;
    q.push(t);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) if (dist[u] == -1) {
            dist[u] = dist[v] + 1;
            q.push(u);
        }
    }
    for (int i = 0; i < n; ++i) disa[i] = -1;
    disa[a] = 0;
    q.push(a);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) if (disa[u] == -1) {
            disa[u] = disa[v] + 1;
            q.push(u);
        }
    }
    for (int i = 0; i < n; ++i) disb[i] = -1;
    disb[b] = 0;
    q.push(b);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int u : adj[v]) if (disb[u] == -1) {
            disb[u] = disb[v] + 1;
            q.push(u);
        }
    }
    if (!chk(0)) {
        cout << -1 << endl;
    } else {
        int l = 0, r = n + 1;
        while (r - l > 1) {
            int mid = l + r >> 1;
            if (chk(mid)) l = mid;
            else r = mid;
        }
        cout << l << endl;
    }
}

Compilation message

007.cpp: In function 'int main()':
007.cpp:77:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |             int mid = l + r >> 1;
      |                       ~~^~~

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9568 KB Output is correct
2 Incorrect 34 ms 10596 KB Output isn't correct
3 Correct 29 ms 9680 KB Output is correct
4 Incorrect 45 ms 10720 KB Output isn't correct
5 Correct 26 ms 9504 KB Output is correct
6 Correct 30 ms 9820 KB Output is correct
7 Correct 31 ms 9996 KB Output is correct
8 Correct 33 ms 10068 KB Output is correct
9 Incorrect 56 ms 10836 KB Output isn't correct
10 Correct 167 ms 16348 KB Output is correct
11 Incorrect 67 ms 12336 KB Output isn't correct
12 Correct 80 ms 13608 KB Output is correct
13 Incorrect 71 ms 12712 KB Output isn't correct
14 Correct 52 ms 11752 KB Output is correct
15 Correct 81 ms 13632 KB Output is correct
16 Correct 94 ms 14080 KB Output is correct
17 Correct 73 ms 13284 KB Output is correct
18 Incorrect 75 ms 13260 KB Output isn't correct
19 Correct 121 ms 15312 KB Output is correct
20 Incorrect 200 ms 18192 KB Output isn't correct
21 Incorrect 153 ms 16260 KB Output isn't correct
22 Correct 102 ms 14936 KB Output is correct
23 Correct 122 ms 16124 KB Output is correct
24 Correct 103 ms 15940 KB Output is correct
25 Incorrect 104 ms 15592 KB Output isn't correct
26 Correct 100 ms 15132 KB Output is correct
27 Correct 127 ms 16220 KB Output is correct
28 Correct 145 ms 16224 KB Output is correct
29 Correct 169 ms 16920 KB Output is correct
30 Incorrect 207 ms 18884 KB Output isn't correct
31 Incorrect 160 ms 17348 KB Output isn't correct
32 Correct 126 ms 16172 KB Output is correct
33 Correct 113 ms 16376 KB Output is correct
34 Incorrect 140 ms 16828 KB Output isn't correct
35 Incorrect 101 ms 16452 KB Output isn't correct
36 Incorrect 115 ms 16760 KB Output isn't correct
37 Correct 152 ms 17788 KB Output is correct
38 Correct 151 ms 17604 KB Output is correct
39 Correct 162 ms 17668 KB Output is correct
40 Incorrect 232 ms 19196 KB Output isn't correct
41 Correct 266 ms 21320 KB Output is correct