oj.uz

Submission #188250

# Submission time Handle Problem Language Result Execution time Memory
188250 2020-01-13T06:57:23 Z qkxwsm 007 (CEOI14_007) C++14
30 / 100
 581 ms 22472 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 = 0, hi = N + 1;
    while(hi > lo)
    {
        int mid = (hi + lo + 1) >> 1;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    ans = lo - 1;
    cout << ans << '\n';
    return 0;
}

Subtask #1
9.0 / 30.0

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

Subtask #2
21.0 / 70.0

# Verdict Execution time Memory Grader output
1 Partially correct 53 ms 7808 KB Partially correct
2 Correct 89 ms 8980 KB Output is correct
3 Partially correct 58 ms 7976 KB Partially correct
4 Correct 89 ms 9208 KB Output is correct
5 Partially correct 61 ms 7840 KB Partially correct
6 Partially correct 60 ms 8128 KB Partially correct
7 Partially correct 67 ms 8372 KB Partially correct
8 Partially correct 74 ms 8436 KB Partially correct
9 Correct 80 ms 9212 KB Output is correct
10 Partially correct 246 ms 17920 KB Partially correct
11 Correct 207 ms 11172 KB Output is correct
12 Partially correct 224 ms 12940 KB Partially correct
13 Correct 130 ms 11648 KB Output is correct
14 Correct 171 ms 10608 KB Output is correct
15 Partially correct 259 ms 12856 KB Partially correct
16 Partially correct 313 ms 13352 KB Partially correct
17 Partially correct 225 ms 12408 KB Partially correct
18 Correct 252 ms 12344 KB Output is correct
19 Partially correct 209 ms 14860 KB Partially correct
20 Correct 380 ms 20712 KB Output is correct
21 Correct 444 ms 15940 KB Output is correct
22 Partially correct 294 ms 14476 KB Partially correct
23 Partially correct 451 ms 15736 KB Partially correct
24 Partially correct 353 ms 15608 KB Partially correct
25 Correct 438 ms 15152 KB Output is correct
26 Partially correct 331 ms 14568 KB Partially correct
27 Partially correct 447 ms 16000 KB Partially correct
28 Partially correct 380 ms 15896 KB Partially correct
29 Partially correct 329 ms 17500 KB Partially correct
30 Correct 406 ms 21952 KB Output is correct
31 Correct 542 ms 17532 KB Output is correct
32 Partially correct 372 ms 15972 KB Partially correct
33 Partially correct 449 ms 16160 KB Partially correct
34 Correct 463 ms 16820 KB Output is correct
35 Correct 550 ms 16248 KB Output is correct
36 Correct 419 ms 16664 KB Output is correct
37 Partially correct 527 ms 18316 KB Partially correct
38 Partially correct 478 ms 18024 KB Partially correct
39 Partially correct 564 ms 18028 KB Partially correct
40 Correct 464 ms 21544 KB Output is correct
41 Partially correct 581 ms 22472 KB Partially correct