oj.uz

Submission #391824

# Submission time Handle Problem Language Result Execution time Memory
391824 2021-04-20T03:21:50 Z abc864197532 007 (CEOI14_007) C++17
0 / 100
 328 ms 19204 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 = 1 << 30;
        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 7324 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 7372 KB Output is correct
7 Correct 5 ms 7372 KB Output is correct
8 Incorrect 6 ms 7372 KB Output isn't correct
9 Correct 5 ms 7316 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 5 ms 7372 KB Output is correct
12 Incorrect 5 ms 7372 KB Output isn't correct
13 Correct 5 ms 7372 KB Output is correct
14 Incorrect 5 ms 7344 KB Output isn't correct
15 Correct 5 ms 7372 KB Output is correct
16 Incorrect 5 ms 7372 KB Output isn't correct
17 Incorrect 5 ms 7372 KB Output isn't correct
18 Incorrect 5 ms 7372 KB Output isn't correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 5 ms 7372 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 5 ms 7372 KB Output is correct
23 Correct 5 ms 7372 KB Output is correct
24 Incorrect 6 ms 7372 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9112 KB Output is correct
2 Incorrect 36 ms 9800 KB Output isn't correct
3 Correct 28 ms 9204 KB Output is correct
4 Incorrect 48 ms 9920 KB Output isn't correct
5 Correct 28 ms 9060 KB Output is correct
6 Correct 33 ms 9284 KB Output is correct
7 Correct 41 ms 9412 KB Output is correct
8 Correct 37 ms 9428 KB Output is correct
9 Incorrect 53 ms 9784 KB Output isn't correct
10 Correct 173 ms 14172 KB Output is correct
11 Incorrect 62 ms 11244 KB Output isn't correct
12 Correct 88 ms 12184 KB Output is correct
13 Incorrect 87 ms 11528 KB Output isn't correct
14 Correct 65 ms 10888 KB Output is correct
15 Correct 77 ms 12288 KB Output is correct
16 Correct 76 ms 12524 KB Output is correct
17 Correct 104 ms 11972 KB Output is correct
18 Incorrect 89 ms 11944 KB Output isn't correct
19 Correct 125 ms 13380 KB Output is correct
20 Incorrect 205 ms 16048 KB Output isn't correct
21 Incorrect 124 ms 14176 KB Output isn't correct
22 Correct 112 ms 13400 KB Output is correct
23 Correct 126 ms 14120 KB Output is correct
24 Correct 113 ms 14032 KB Output is correct
25 Incorrect 111 ms 13732 KB Output isn't correct
26 Correct 113 ms 13368 KB Output is correct
27 Correct 140 ms 14140 KB Output is correct
28 Correct 146 ms 14160 KB Output is correct
29 Correct 169 ms 14712 KB Output is correct
30 Incorrect 249 ms 16804 KB Output isn't correct
31 Incorrect 160 ms 15264 KB Output isn't correct
32 Correct 148 ms 14176 KB Output is correct
33 Correct 135 ms 14436 KB Output is correct
34 Incorrect 158 ms 14732 KB Output isn't correct
35 Incorrect 131 ms 14456 KB Output isn't correct
36 Incorrect 126 ms 14680 KB Output isn't correct
37 Correct 166 ms 15616 KB Output is correct
38 Correct 162 ms 15468 KB Output is correct
39 Correct 182 ms 15460 KB Output is correct
40 Incorrect 229 ms 17112 KB Output isn't correct
41 Correct 328 ms 19204 KB Output is correct