Submission #490315

#	Time	Username	Problem	Language	Result	Execution time	Memory
490315		SirCovidThe19th	007 (CEOI14_007)	C++17	100 / 100	394 ms	16196 KiB

007

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

const int mx = 2e5 + 5;

int n, m, s, v, a, b, dA[mx], dB[mx], ans; vector<int> adj[mx];

void bfs(int st, int *D){
    queue<int> Q; fill(D, D + n + 1, -1); 
    Q.push(st); D[st] = 0;
    while (!Q.empty()){
        int i = Q.front(); Q.pop();
        for (int j : adj[i]) if (D[j] == -1) D[j] = D[i] + 1, Q.push(j);
    }
}
int same(int pos){
    int d = 0;
    while (1){
        bool ok = 0;
        for (int i : adj[pos]) if (dA[i] < dA[pos] and dB[i] < dB[pos]){
            pos = i; ok = 1; d++; 
            break;
        }
        if (!ok) break;
    }
    return d;
}

int main(){
    cin >> n >> m >> s >> v >> a >> b;
    for (int i = 1; i <= m; i++){
        int a, b; cin >> a >> b;
        adj[a].push_back(b); adj[b].push_back(a);
    }
    bfs(a, dA); bfs(b, dB);
    int wA = dA[v] - dA[s], wB = dB[v] - dB[s];

    if (wA == wB) ans = (same(s) + wA < same(v) ? wA - 1 : wA);
    else ans = min(wA, wB);

    cout<<max(ans, -1)<<endl;
}

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