This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb emplace_back
#define ll long long
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
const int N = int(2e5) + 7;
const int logN = 18;
typedef pair<int, int> pii;
int n, m, s, d, a, b, diff1, diff2;
vector<int> adj[N], dis[2];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#define Task "test"
if(fopen(Task".inp", "r")) {
freopen(Task".inp", "r", stdin);
freopen(Task".out", "w", stdout);
}
cin >> n >> m >> s >> d >> a >> b;
for(int u, v, i = 1; i <= m; ++i) {
cin >> u >> v;
adj[u].pb(v), adj[v].pb(u);
}
function<void(int, vector<int>&)> bfs = [&](int s, vector<int>& d) {
queue<int> q; d.resize(n + 1, 1e9);
d[s] = 0;
for(q.push(s); q.size(); q.pop()) {
s = q.front();
for(int v: adj[s]) {
if(d[v] > d[s] + 1)
d[v] = d[s] + 1, q.push(v);
}
}
};
bfs(a, dis[0]), bfs(b, dis[1]);
diff1 = dis[0][d] - dis[0][s];
diff2 = dis[1][d] - dis[1][s];
if(diff1 != diff2) cout << max(-1, min(diff1, diff2));
else {
function<int(int)> bfs = [&](int s) {
vector<int> d; d.resize(n + 1, 1e9);
queue<int> q; d[s] = 0;
for(q.push(s); q.size(); q.pop()) {
s = q.front();
for(int v: adj[s]) {
if(dis[0][v] == dis[0][s] - 1 && dis[0][v] == dis[1][v] && d[v] == 1e9)
q.push(v), d[v] = d[s] + 1;
}
}
return d[s];
};
cout << max(-1, diff1 - (diff1 + bfs(s) < bfs(d)));
}
}
Compilation message (stderr)
007.cpp: In function 'int32_t main()':
007.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".inp", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
007.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(Task".out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |