# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
82368 | minhtung0404 | 007 (CEOI14_007) | C++17 | 640 ms | 15916 KiB |
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>
const int N = 2e5 + 5;
using namespace std;
vector <int> adj[N];
int n, m, s, d, a, b;
int ck[N];
bool check(int num){
for (int i = 1; i <= n; i++) ck[i] = 0;
queue <int> mq, mq2; mq.push(d); ck[d] = 1;
while (mq.size()){
int u = mq.front();
if (ck[u] == num+1) break;
mq.pop();
for (auto v : adj[u]){
if (ck[v]) continue;
ck[v] = ck[u] + 1;
mq.push(v);
}
}
if (ck[a] || ck[b]) return false;
mq2.push(s); ck[s] = -1; int cnt = 1;
while (mq2.size()){
while (mq.size()){
int u = mq.front();
if (ck[u] == num+cnt+1) break;
mq.pop();
if (ck[u] < 0) continue;
for (auto v : adj[u]){
if (ck[v]) continue;
ck[v] = ck[u] + 1;
mq.push(v);
}
}
while (mq2.size()){
int u = mq2.front();
if (-ck[u] == cnt+1) break;
mq2.pop();
for (auto v : adj[u]){
if (ck[v] < 0) continue;
ck[v] = ck[u] - 1;
mq2.push(v);
}
}
if (ck[a] > 0 || ck[b] > 0) return false;
cnt++;
}
return true;
}
int main(){
// freopen("SPY.inp", "r", stdin);
// freopen("SPY.out", "w", stdout);
scanf("%d %d", &n, &m);
scanf("%d %d %d %d", &s, &d, &a, &b);
for (int i = 1; i <= m; i++){
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
int l = 0, r = n + 1, ans = -1;
while (l != r){
int mid = (l + r + 1) / 2;
if (check(mid)){
ans = mid;
l = mid;
}
else{
r = mid-1;
}
}
if (check(l)) ans = l;
printf("%d", ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |