Submission #490530

#	Time	Username	Problem	Language	Result	Execution time	Memory
490530		SirCovidThe19th	007 (CEOI14_007)	C++17	100 / 100	187 ms	19344 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 nearer(int src){
	queue<int> Q; int D[n + 1], ret = 0; 
	fill(D, D + n + 1, -1); D[src] = 0; Q.push(src);
	while (!Q.empty()){
		int i = Q.front(); Q.pop();
		for (int j : adj[i]) if (D[j] == -1 and dA[j] < dA[i] and dB[j] < dB[i]){
            D[j] = D[i] + 1; ret = max(ret, D[i]);
            Q.push(j);
        }
	}
	return ret;
}
 
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); 
    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 = (nearer(s) < nearer(v) - wA) ? wA - 1 : wA;
    else ans = min(wA, wB);
 
    cout<<max(ans, -1)<<endl;
}

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