oj.uz

Submission #391828

# Submission time Handle Problem Language Result Execution time Memory
391828 2021-04-20T03:23:00 Z abc864197532 007 (CEOI14_007) C++17
0 / 100
 1000 ms 19268 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);
        }
    }
    for (int i = 0; i <= n; ++i) if (!chk(i)) {
        cout << i - 1 << endl;
        return 0;
    }
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7372 KB Output is correct
2 Correct 5 ms 7328 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 5 ms 7372 KB Output is correct
7 Correct 5 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 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 7372 KB Output isn't correct
15 Correct 5 ms 7372 KB Output is correct
16 Incorrect 6 ms 7372 KB Output isn't correct
17 Incorrect 6 ms 7372 KB Output isn't correct
18 Incorrect 5 ms 7372 KB Output isn't correct
19 Correct 5 ms 7396 KB Output is correct
20 Correct 5 ms 7372 KB Output is correct
21 Correct 5 ms 7376 KB Output is correct
22 Correct 5 ms 7372 KB Output is correct
23 Correct 5 ms 7372 KB Output is correct
24 Incorrect 5 ms 7308 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9068 KB Output is correct
2 Incorrect 68 ms 9800 KB Output isn't correct
3 Correct 27 ms 9100 KB Output is correct
4 Incorrect 103 ms 9972 KB Output isn't correct
5 Correct 27 ms 9004 KB Output is correct
6 Correct 33 ms 9212 KB Output is correct
7 Correct 30 ms 9480 KB Output is correct
8 Correct 32 ms 9420 KB Output is correct
9 Incorrect 43 ms 9816 KB Output isn't correct
10 Correct 136 ms 14200 KB Output is correct
11 Incorrect 67 ms 11260 KB Output isn't correct
12 Correct 74 ms 12184 KB Output is correct
13 Incorrect 69 ms 11564 KB Output isn't correct
14 Correct 58 ms 10820 KB Output is correct
15 Correct 142 ms 12320 KB Output is correct
16 Correct 123 ms 12612 KB Output is correct
17 Correct 134 ms 12036 KB Output is correct
18 Incorrect 76 ms 11996 KB Output isn't correct
19 Correct 100 ms 13232 KB Output is correct
20 Incorrect 184 ms 16068 KB Output isn't correct
21 Incorrect 711 ms 14392 KB Output isn't correct
22 Correct 95 ms 13268 KB Output is correct
23 Execution timed out 1087 ms 14096 KB Time limit exceeded
24 Correct 130 ms 14020 KB Output is correct
25 Incorrect 109 ms 13688 KB Output isn't correct
26 Correct 477 ms 13508 KB Output is correct
27 Correct 167 ms 14148 KB Output is correct
28 Correct 117 ms 14252 KB Output is correct
29 Correct 147 ms 14788 KB Output is correct
30 Incorrect 200 ms 16720 KB Output isn't correct
31 Incorrect 492 ms 15296 KB Output isn't correct
32 Correct 124 ms 14144 KB Output is correct
33 Correct 372 ms 14532 KB Output is correct
34 Incorrect 135 ms 14736 KB Output isn't correct
35 Execution timed out 1085 ms 14380 KB Time limit exceeded
36 Incorrect 128 ms 14884 KB Output isn't correct
37 Correct 955 ms 15744 KB Output is correct
38 Correct 157 ms 15604 KB Output is correct
39 Correct 162 ms 15456 KB Output is correct
40 Incorrect 278 ms 17060 KB Output isn't correct
41 Correct 270 ms 19268 KB Output is correct