Submission #82419

#TimeUsernameProblemLanguageResultExecution timeMemory
82419Flying_dragon_02007 (CEOI14_007)C++14
0 / 100
373 ms16524 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second typedef pair<int, int> ii; const int N = 2e5 + 5, inf = 1e9 + 123; int n, m, src[2], a[2], d[2][N], l = -1, r = 6e5 + 5; vector<int> gr[N]; void dijkstra (bool _) { for (int i = 1; i <= n; ++i) d[_][i] = inf; d[_][ src[_] ] = 0; priority_queue<ii, vector<ii>, greater<ii> > pq; pq.push(ii(d[_][ src[_] ], src[_]) ); while (!pq.empty() ) { ii tmp = pq.top(); pq.pop(); int u = tmp.se; if (tmp.fi > d[_][u]) continue ; for (int v : gr[u]) { if (d[_][v] > d[_][u] + 1) { d[_][v] = d[_][u] + 1; pq.push(ii(d[_][v], v) ); } } } } bool check (int Time) { d[1][ a[0] ] -= Time; d[1][ a[1] ] -= Time; if (d[0][ a[0] ] > d[1][ a[0] ] || d[0][ a[1] ] > d[1][ a[1] ]) { d[1][ a[0] ] += Time; d[1][ a[1] ] += Time; return false; } d[1][ a[0] ] += Time; d[1][ a[1] ] += Time; return true; } int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("SPY.INP", "r", stdin); //freopen("SPY.OUT", "w", stdout); cin >> n >> m; cin >> src[0] >> src[1] >> a[0] >> a[1]; while (m --) { int u, v; cin >> u >> v; gr[u].pb(v); gr[v].pb(u); } dijkstra(0); dijkstra(1); while (l < r) { int mid = (l + r + 1) / 2; if (check(mid) ) l = mid; else r = mid - 1; } cout << l; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...