This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 200000;
int N, M;
int me, him, sv1, sv2;
vector <int> adj[N_MAX + 2];
void bfs (int start, int dist[]) {
fill(dist + 1, dist + N + 1, INT_MAX);
queue <int> q;
dist[start] = 0;
q.push(start);
while (q.empty() == false) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] == INT_MAX) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
int dist1[N_MAX + 2];
int dist2[N_MAX + 2];
int dfs (int u) {
int ret = 0;
for (int v : adj[u]) {
if (dist1[u] > dist1[v] && dist2[u] > dist2[v]) {
ret = max(ret, dfs(v) + 1);
}
}
return ret;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
cin >> me >> him >> sv1 >> sv2;
for (int i = 1; i <= M; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
bfs(sv1, dist1);
bfs(sv2, dist2);
int wait1 = dist1[him] - dist1[me];
int wait2 = dist2[him] - dist2[me];
int wait;
if (wait1 != wait2) {
wait = min(wait1, wait2);
} else {
int decme = dfs(me);
int dechim = dfs(him);
if (wait1 + decme >= dechim) {
wait = wait1;
} else {
wait = wait1 + 1;
}
}
cout << (wait >= 0 ? wait : -1) << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |