Submission #125802

#	Time	Username	Problem	Language	Result	Execution time	Memory
125802		lyc	007 (CEOI14_007)	C++14	100 / 100	366 ms	25080 KiB

007

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 2e5+5;

int N,M,S,D,A,B;
vector<int> al[MAXN];
int dS[MAXN], dD[MAXN], dA[MAXN], dB[MAXN];

void bfs(int x, int d[]) {
    FOR(i,1,N) d[i] = -1;
    queue<int> q;
    d[x] = 0; q.push(x);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (auto v : al[u]) if (d[v] == -1) d[v] = d[u]+1, q.push(v);
    }
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> M;
    cin >> S >> D >> A >> B;
    FOR(i,1,M){
        int U, V; cin >> U >> V;
        al[U].push_back(V);
        al[V].push_back(U);
    }

    bfs(S, dS);
    bfs(D, dD);
    bfs(A, dA);
    bfs(B, dB);
    if (dS[A] > dD[A] || dS[B] > dD[B]) cout << -1 << '\n';
    else {
        int ans = min(dD[A]-dS[A], dD[B]-dS[B]);

        int sS = S, sD = D;
        FOR(i,1,N) {
            if (dS[i] + dA[i] == dS[A] && dS[i] + dB[i] == dS[B]) sS = (dS[sS] > dS[i] ? sS : i);
            if (dD[i] + dA[i] == dD[A] && dD[i] + dB[i] == dD[B]) sD = (dD[sD] > dD[i] ? sD : i);
        }

        //cout << ans << " :: " << sS << " " << sD << endl;
        if (dS[A] == dS[B] && dD[A] == dD[B] && sS != sD && dS[sS] < dD[sD]-ans) ans -= 1;
        cout << ans << '\n';
    }
}

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