Submission #117064

#TimeUsernameProblemLanguageResultExecution timeMemory
117064JohnTitor007 (CEOI14_007)C++11
100 / 100
272 ms17656 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, j, k) for(int i=(j); i<=(k); i++) #define FFOR(i, j, k) for(int i=(j); i<(k); i++) #define DFOR(i, j, k) for(int i=(j); i>=(k); i--) #define bug(x) cerr<<#x<<" = "<<(x)<<'\n' #define pb push_back #define mp make_pair #define bit(s, i) (((s)>>(i))&1LL) #define mask(i) ((1LL<<(i))) #define builtin_popcount __builtin_popcountll #define __builtin_popcount __builtin_popcountll using ll=long long; using ld=long double; mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2; template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;} template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);} template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);} template <typename T> inline void writeln(T x){write(x); putchar('\n');} #define taskname "007" int n, m; int s, d, a, b; int a1, a2, b1, b2, w1, w2; int fa[200001]; bool donea[200001]; int fb[200001]; bool doneb[200001]; vector <int> g[200001]; queue <int> q; void bfs(int s, int *f, bool *done){ FOR(i, 1, n) done[i]=0; f[s]=0; done[s]=1; q.push(s); while(!q.empty()){ s=q.front(); q.pop(); for(int v: g[s]) if(!done[v]){ done[v]=1; f[v]=f[s]+1; q.push(v); } } } int dp[200001]; bool done[200001]; int DP(int u){ if(done[u]) return dp[u]; done[u]=1; for(int v: g[u]) if(fa[v]<fa[u]&&fb[v]<fb[u]) dp[u]=max(dp[u], DP(v)+1); return dp[u]; } int main(){ #ifdef Aria if(fopen(taskname".in", "r")) freopen(taskname".in", "r", stdin); #endif // Aria read(n); read(m); read(s); read(d); read(a); read(b); { int u, v; FOR(i, 1, m){ read(u); read(v); g[u].pb(v); g[v].pb(u); } } bfs(a, fa, donea); bfs(b, fb, doneb); a1=fa[s]; a2=fa[d]; b1=fb[s]; b2=fb[d]; w1=a2-a1; w2=b2-b1; if(w1<0||w2<0){ puts("-1"); return 0; } else if(w1!=w2){ writeln(min(w1, w2)); } else{ int x=DP(s); int y=DP(d); if(x+w1>=y) writeln(w1); else writeln(w1-1); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...