Submission #110790

#	Time	Username	Problem	Language	Result	Execution time	Memory
110790		ckodser	007 (CEOI14_007)	C++14	0 / 100	487 ms	26428 KiB

007

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=2e5+500;
const ll inf=1e9+900;

vector<ll> ger[maxn];
ll fs[maxn];
ll fd[maxn];
ll fa[maxn];
ll fb[maxn];
bool vis[maxn];

void bfs(ll a,ll* f){
    queue<ll> qu;
    memset(vis,0,sizeof vis);
    qu.push(a);
    vis[a]=1;
    while(qu.size()){
	ll v=qu.front();
	qu.pop();
	for(auto u:ger[v]){
	    if(!vis[u]){
		vis[u]=1;
		f[u]=f[v]+1;
		qu.push(u);
	    }
	}
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,m;
    cin>>n>>m;
    ll s,d,a,b;
    cin>>s>>d>>a>>b;
    for(ll i=0;i<m;i++){
	ll a,b;
	cin>>a>>b;
	ger[a].pb(b);
	ger[b].pb(a);
    }
    bfs(s,fs);
    bfs(d,fd);
    bfs(a,fa);
    bfs(b,fb);

    if(fd[a]!=fd[b] || fs[a]!=fs[b]){
	ll r1=fd[a];
	ll r2=fd[b];
	ll w1=fs[a];
	ll w2=fs[b];
	if(r1>r2){
	    swap(r1,r2);
	    swap(w1,w2);
	}	
	ll ans=min(r1-w1,r2-w2);
	if(ans<0){
	    ans=-1;
	}
	cout<<ans<<endl;
    }else{
	ll mxd=0;
	for(ll i=1;i<=n;i++){
	    if(fd[i]+fa[i]==fd[a] && fd[i]+fb[i]==fd[a]){
		mxd=max(mxd,fd[i]);
	    }
	}
	ll mxs=0;
	for(ll i=1;i<=n;i++){
	    if(fs[i]+fa[i]==fs[a] && fs[i]+fb[i]==fs[b]){
		mxs=max(mxs,fs[i]);
	    }
	}
	ll q=mxd;
	ll w=fd[a]-mxd;
	ll e=mxs;
	ll r=fs[a]-mxs;
	ll r1=fd[a];
	ll w1=fs[a];
	ll x=r1-w1-1;
	if(x<0){
	    cout<<-1<<endl;
	}else{
	    cout<<x-1<<endl;
	}
	
    }	
}

Compilation message (stderr)

007.cpp: In function 'int main()':
007.cpp:85:5: warning: unused variable 'q' [-Wunused-variable]
  ll q=mxd;
     ^
007.cpp:86:5: warning: unused variable 'w' [-Wunused-variable]
  ll w=fd[a]-mxd;
     ^
007.cpp:87:5: warning: unused variable 'e' [-Wunused-variable]
  ll e=mxs;
     ^
007.cpp:88:5: warning: unused variable 'r' [-Wunused-variable]
  ll r=fs[a]-mxs;
     ^

• Subtask 1: 0 / 30
• Subtask 2: 0 / 70