Submission #90721

#	Time	Username	Problem	Language	Result	Execution time	Memory
90721		combi2k2	007 (CEOI14_007)	C++14	100 / 100	307 ms	17372 KiB

007

#include<bits/stdc++.h>

using namespace std;

const int   N   = 2e5 + 1;

vector<int> g[N];

int fa[N];
int fb[N];
int n;

int bfs(int s,int d[])  {
    fill(d + 1,d + 1 + n,-1);

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

    while(q.size()) {
        int u = q.front();  q.pop();
        for(int v : g[u])
            if (d[v] < 0)   {
                d[v] = d[u] + 1;
                q.push(v);
            }
    }

    return  1;
}
int go(int s)   {
    vector<int> d(n + 1,-1);
    d[s] = -1;
    queue<int>  q;
    q.push(s);
    int ans = 0;
    while(q.size()) {
        int u = q.front();  q.pop();
        for(int v : g[u])
            if (fa[v] + 1 == fa[u] && fb[v] + 1 == fb[u] && d[v] < 0)   {
                d[v] = d[u] + 1;
                ans = max(ans,d[v]);
                q.push(v);
            }
    }
    return  ans;
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int m, s, d, a, b;

    cin >> n >> m >> s >> d >> a >> b;

    while (m--) {
        int x, y;   cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    bfs(a,fa);
    bfs(b,fb);

    int dA = fa[d] - fa[s];
    int dB = fb[d] - fb[s];

    if (dA != dB)   cout << max(min(dA,dB),-1);
    if (dA == dB)   cout << max(dA - (dA + go(s) < go(d)),-1);
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70