Submission #171597

#TimeUsernameProblemLanguageResultExecution timeMemory
171597MvC007 (CEOI14_007)C++11
30 / 100
329 ms17484 KiB
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=2e5+50; const int mod=1e9+7; using namespace std; int n,m,s[2],a[2],d[2][nmax],x,y,mn,i,j; vector<int>g[nmax]; queue<pair<int,int> >q; pair<int,int>p; int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m; cin>>s[0]>>s[1]>>a[0]>>a[1]; while(m--) { cin>>x>>y; g[x].pb(y); g[y].pb(x); } for(j=0;j<2;j++) { for(i=1;i<=n;i++)d[j][i]=inf; q.push(mkp(s[j],0)); d[j][s[j]]=0; while(!q.empty()) { p=q.front(); q.pop(); for(i=0;i<(int)g[p.fr].size();i++) { x=g[p.fr][i]; if(d[j][x]!=inf)continue; d[j][x]=p.sc+1; q.push(mkp(x,d[j][x])); } } } mn=inf; for(i=0;i<2;i++) { x=a[i]; mn=min(mn,d[1][x]-d[0][x]); } if(mn<-1)mn=-1; if(mn!=-1 && d[0][a[0]]==d[0][a[1]] && d[1][a[0]]==d[1][a[1]])mn--; cout<<mn<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...