Submission #52341

#	Time	Username	Problem	Language	Result	Execution time	Memory
52341		Alexa2001	007 (CEOI14_007)	C++17	100 / 100	330 ms	16556 KiB

007

#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==c && b==d); /// sa ma aigur ca totusi n-am scapat ceva

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

    return 1;
}

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: 30 / 30
• Subtask 2: 70 / 70