oj.uz

Submission #52335

# Submission time Handle Problem Language Result Execution time Memory
52335 2018-06-25T12:50:39 Z Alexa2001 007 (CEOI14_007) C++17
0 / 100
 487 ms 27944 KB 
#include <bits/stdc++.h>

using namespace std;
/// 15:26

const int Nmax = 2e5 + 5, inf = 2e9;

int n, m, A, B, S, D, i, x, y;
int dist1[Nmax], dist2[Nmax];
vector<int> v[Nmax];

bool adv(int &node)
{
    for(auto it : v[node])
        if(dist1[it] == dist1[node] - 1 && dist2[it] == dist2[node] - 1)
        {
            node = it;
            return 1;
        }
    return 0;
}

bool win(int tmp)
{
    int a, b, c, d;
    a = dist1[D], b = dist2[D];
    c = dist1[S] + tmp, d = dist2[S] + tmp;

    if(a < c || b < d) return 0;
    if(c < a && c < b) return 1;
    if(d < a && d < b) return 1;
    if(a == c && b > d) return 1;
    if(b == d && a > c) return 1;

    /// pana aici totul e frumos, iese pe hartie
    /// si acum vine cazul naspa, cireasa de pe tort
    /// avem a = c si b = d
    /// trebuie sa vedem care dintre aia doi ajunge primul la un nod care nu mai are continuare echidistanta fata de A si B
    /// cred ca nu se intersecteaza pe parcurs, cred...

    assert(a==b && c==d && a==b); /// sa ma aigur ca totusi n-am scapat ceva

    int i, ss = S, dd = D;
    for(i=1; i<=a; ++i)
    {
        if(!adv(ss)) return 1;
        if(i<=tmp) continue;
        if(!adv(dd)) return 0;
    }
    assert(0);
}

int solve()
{
    int st = 0, dr = n, mid;
    while(st <= dr)
    {
        mid = (st+dr)/2;
        if(!win(mid)) dr = mid-1;
            else st = mid+1;
    }
    return dr;
}

void calc(int node, int d[])
{
    int i;
    for(i=1; i<=n; ++i) d[i] = inf;

    queue<int> q;
    d[node] = 0;
    q.push(node);

    while(q.size())
    {
        node = q.front();
        q.pop();
        for(auto it : v[node])
            if(d[it] == inf)
            {
                d[it] = d[node] + 1;
                q.push(it);
            }
    }
}

int main()
{
  //  freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n >> m;
    cin >> S >> D >> A >> B;

    for(i=1; i<=m; ++i)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    calc(A, dist1);
    calc(B, dist2);

    cout << solve() << '\n';

    return 0;
}

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4984 KB Output is correct
2 Runtime error 13 ms 9956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 8 ms 10096 KB Output is correct
4 Incorrect 8 ms 10096 KB Output isn't correct
5 Incorrect 8 ms 10096 KB Output isn't correct
6 Correct 8 ms 10096 KB Output is correct
7 Correct 8 ms 10096 KB Output is correct
8 Incorrect 10 ms 10096 KB Output isn't correct
9 Correct 7 ms 10136 KB Output is correct
10 Correct 7 ms 10136 KB Output is correct
11 Correct 7 ms 10140 KB Output is correct
12 Incorrect 8 ms 10160 KB Output isn't correct
13 Correct 8 ms 10160 KB Output is correct
14 Incorrect 8 ms 10160 KB Output isn't correct
15 Correct 7 ms 10160 KB Output is correct
16 Incorrect 9 ms 10160 KB Output isn't correct
17 Incorrect 8 ms 10220 KB Output isn't correct
18 Incorrect 7 ms 10336 KB Output isn't correct
19 Correct 9 ms 10336 KB Output is correct
20 Correct 8 ms 10336 KB Output is correct
21 Correct 7 ms 10336 KB Output is correct
22 Correct 8 ms 10336 KB Output is correct
23 Correct 7 ms 10336 KB Output is correct
24 Incorrect 8 ms 10336 KB Output isn't correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11780 KB Output is correct
2 Incorrect 54 ms 12420 KB Output isn't correct
3 Correct 39 ms 12420 KB Output is correct
4 Incorrect 72 ms 12548 KB Output isn't correct
5 Correct 39 ms 12548 KB Output is correct
6 Correct 44 ms 12548 KB Output is correct
7 Correct 44 ms 12548 KB Output is correct
8 Partially correct 48 ms 12548 KB Partially correct
9 Incorrect 91 ms 12688 KB Output isn't correct
10 Correct 269 ms 16980 KB Output is correct
11 Incorrect 101 ms 16980 KB Output isn't correct
12 Correct 121 ms 16980 KB Output is correct
13 Incorrect 98 ms 16980 KB Output isn't correct
14 Correct 71 ms 16980 KB Output is correct
15 Correct 129 ms 16980 KB Output is correct
16 Correct 129 ms 16980 KB Output is correct
17 Correct 100 ms 16980 KB Output is correct
18 Incorrect 124 ms 16980 KB Output isn't correct
19 Correct 180 ms 16980 KB Output is correct
20 Incorrect 307 ms 18452 KB Output isn't correct
21 Incorrect 177 ms 18452 KB Output isn't correct
22 Correct 152 ms 18452 KB Output is correct
23 Runtime error 192 ms 22608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Correct 159 ms 22608 KB Output is correct
25 Incorrect 156 ms 22608 KB Output isn't correct
26 Runtime error 140 ms 22608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Correct 164 ms 22608 KB Output is correct
28 Partially correct 178 ms 22608 KB Partially correct
29 Correct 233 ms 22684 KB Output is correct
30 Incorrect 373 ms 24716 KB Output isn't correct
31 Incorrect 188 ms 24716 KB Output isn't correct
32 Correct 190 ms 24716 KB Output is correct
33 Runtime error 190 ms 24716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Incorrect 196 ms 24716 KB Output isn't correct
35 Incorrect 230 ms 24716 KB Output isn't correct
36 Incorrect 169 ms 24716 KB Output isn't correct
37 Correct 224 ms 24716 KB Output is correct
38 Correct 226 ms 24716 KB Output is correct
39 Correct 240 ms 24716 KB Output is correct
40 Incorrect 336 ms 25844 KB Output isn't correct
41 Correct 487 ms 27944 KB Output is correct