oj.uz

Submission #188249

# Submission time Handle Problem Language Result Execution time Memory
188249 2020-01-13T06:56:52 Z qkxwsm 007 (CEOI14_007) C++14
0 / 100
 597 ms 26608 KB 
#include <bits/stdc++.h>

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define MAXN 200013
#define INF 1000000007

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, M, S, T, A, B;
vi edge[MAXN];
vi ds, dt, da, db;
int dis[MAXN];
int ans;

void bfs(int s, vi &dist)
{
    FOR(i, 0, N) dist[i] = INF;
    queue<int> q; q.push(s); dist[s] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for (int v : edge[u])
        {
            if (dist[v] > dist[u] + 1)
            {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}
bool check(int x)
{
    queue<int> q;
    FOR(i, 0, N)
    {
        if (dt[i] <= x)
        {
            dis[i] = 0;
            q.push(i);
        }
        else dis[i] = INF;
    }
    //they start at T, you start at S.
    //they need to be able to reach A or B at least one second before you.
    // if (dis[A] == 0 || dis[B] == 0) return false;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for (int v : edge[u])
        {
            //can i go to v?
            if (dis[v] > dis[u] + 1 && ds[v] > dis[u] + 1)
            {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return (dis[A] == INF && dis[B] == INF);
    //they can start at any place marked ok.
    //they go, then you go.
}

int32_t main()
{
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(4);
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> M >> S >> T >> A >> B; S--; T--; A--; B--;
    assert(S != A && S != B && T != A && T != B);
    FOR(i, 0, M)
    {
        int u, v;
        cin >> u >> v;
        u--; v--;
        edge[u].PB(v);
        edge[v].PB(u);
    }
    ds.resize(N); dt.resize(N); da.resize(N); db.resize(N);
    bfs(S, ds);
    bfs(T, dt);
    bfs(A, da);
    bfs(B, db);
    int lo = -1, hi = N + 1;
    while(hi > lo)
    {
        int mid = (hi + lo + 1) >> 1;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    ans = lo;
    cout << ans << '\n';
    return 0;
}

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 7840 KB Output is correct
2 Incorrect 77 ms 9104 KB Output isn't correct
3 Correct 57 ms 8008 KB Output is correct
4 Incorrect 80 ms 9208 KB Output isn't correct
5 Correct 55 ms 7748 KB Output is correct
6 Correct 57 ms 8104 KB Output is correct
7 Correct 61 ms 8364 KB Output is correct
8 Correct 70 ms 8480 KB Output is correct
9 Incorrect 78 ms 9212 KB Output isn't correct
10 Correct 267 ms 18096 KB Output is correct
11 Incorrect 212 ms 11140 KB Output isn't correct
12 Correct 207 ms 12828 KB Output is correct
13 Incorrect 119 ms 11696 KB Output isn't correct
14 Correct 145 ms 10616 KB Output is correct
15 Correct 217 ms 12948 KB Output is correct
16 Correct 278 ms 13304 KB Output is correct
17 Correct 221 ms 12408 KB Output is correct
18 Incorrect 272 ms 12408 KB Output isn't correct
19 Correct 359 ms 15032 KB Output is correct
20 Incorrect 357 ms 20764 KB Output isn't correct
21 Incorrect 413 ms 15928 KB Output isn't correct
22 Correct 282 ms 14556 KB Output is correct
23 Correct 418 ms 15736 KB Output is correct
24 Correct 337 ms 15608 KB Output is correct
25 Incorrect 344 ms 15244 KB Output isn't correct
26 Correct 297 ms 14728 KB Output is correct
27 Correct 394 ms 15920 KB Output is correct
28 Correct 394 ms 16036 KB Output is correct
29 Correct 315 ms 17568 KB Output is correct
30 Incorrect 453 ms 21964 KB Output isn't correct
31 Incorrect 547 ms 17500 KB Output isn't correct
32 Correct 378 ms 15976 KB Output is correct
33 Correct 593 ms 16268 KB Output is correct
34 Incorrect 460 ms 16820 KB Output isn't correct
35 Incorrect 450 ms 16248 KB Output isn't correct
36 Incorrect 407 ms 16804 KB Output isn't correct
37 Correct 547 ms 18388 KB Output is correct
38 Correct 469 ms 18000 KB Output is correct
39 Correct 522 ms 18156 KB Output is correct
40 Incorrect 464 ms 21560 KB Output isn't correct
41 Correct 597 ms 26608 KB Output is correct