Submission #110791

#	Time	Username	Problem	Language	Result	Execution time	Memory
110791		ckodser	007 (CEOI14_007)	C++14	100 / 100	377 ms	19320 KiB

007

#include<bits/stdc++.h>

#define ll int
#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=1e5+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);
	    }
	}
    }
}
bool is_ok(ll q,ll w,ll e,ll r){
	if(e>=q){
	    if(e+r>w+q){
		return 0;
	    }else{
		return 1;
	    }
	}else{
	    if(e+r+1>w+q){
		return 0;
	    }else{
		return 1;
	    }	
	}

}
pii find_new(ll mid,ll q,ll w){
    if(q>=mid){
	return mp(q-mid,w);
    }
    mid-=q;
    q=0;
    return mp(0,w-mid);
}	
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;
	if(!is_ok(q,w,e,r)){
	    cout<<-1;
	    return 0;
	}
	ll s=0;
	ll t=inf;
	while(t-s>1){
	    ll mid=(s+t)/2;
	    pii tr=find_new(mid,q,w);
	    if(is_ok(tr.F,tr.S,e,r)){
		s=mid;
	    }else{
		t=mid;
	    }
	}
	cout<<s;
	return 0;
    }	
}

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