oj.uz

Submission #110790

# Submission time Handle Problem Language Result Execution time Memory
110790 2019-05-12T08:27:45 Z ckodser 007 (CEOI14_007) C++14
0 / 100
 487 ms 26428 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5248 KB Output is correct
2 Correct 6 ms 5248 KB Output is correct
3 Partially correct 6 ms 5248 KB Partially correct
4 Partially correct 7 ms 5248 KB Partially correct
5 Partially correct 7 ms 5248 KB Partially correct
6 Incorrect 6 ms 5248 KB Output isn't correct
7 Incorrect 6 ms 5248 KB Output isn't correct
8 Partially correct 7 ms 5248 KB Partially correct
9 Incorrect 12 ms 5248 KB Output isn't correct
10 Correct 7 ms 5248 KB Output is correct
11 Correct 6 ms 5248 KB Output is correct
12 Partially correct 7 ms 5376 KB Partially correct
13 Incorrect 7 ms 5376 KB Output isn't correct
14 Partially correct 7 ms 5248 KB Partially correct
15 Incorrect 6 ms 5376 KB Output isn't correct
16 Partially correct 7 ms 5376 KB Partially correct
17 Partially correct 7 ms 5376 KB Partially correct
18 Partially correct 7 ms 5248 KB Partially correct
19 Incorrect 6 ms 5248 KB Output isn't correct
20 Incorrect 8 ms 5376 KB Output isn't correct
21 Correct 8 ms 5248 KB Output is correct
22 Incorrect 7 ms 5376 KB Output isn't correct
23 Incorrect 6 ms 5376 KB Output isn't correct
24 Partially correct 7 ms 5372 KB Partially correct

Subtask #2
0.0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 7800 KB Output isn't correct
2 Partially correct 72 ms 9016 KB Partially correct
3 Incorrect 49 ms 8056 KB Output isn't correct
4 Partially correct 60 ms 9080 KB Partially correct
5 Correct 38 ms 7800 KB Output is correct
6 Correct 44 ms 8056 KB Output is correct
7 Incorrect 48 ms 8440 KB Output isn't correct
8 Incorrect 30 ms 8448 KB Output isn't correct
9 Partially correct 61 ms 9592 KB Partially correct
10 Incorrect 226 ms 18424 KB Output isn't correct
11 Partially correct 84 ms 11000 KB Partially correct
12 Incorrect 137 ms 12724 KB Output isn't correct
13 Partially correct 130 ms 11488 KB Partially correct
14 Correct 89 ms 10460 KB Output is correct
15 Incorrect 113 ms 12636 KB Output isn't correct
16 Correct 92 ms 12920 KB Output is correct
17 Incorrect 82 ms 12152 KB Output isn't correct
18 Partially correct 130 ms 12152 KB Partially correct
19 Incorrect 148 ms 15224 KB Output isn't correct
20 Partially correct 348 ms 21268 KB Partially correct
21 Partially correct 188 ms 15352 KB Partially correct
22 Incorrect 155 ms 14172 KB Output isn't correct
23 Correct 156 ms 15296 KB Output is correct
24 Incorrect 192 ms 15200 KB Output isn't correct
25 Partially correct 139 ms 14556 KB Partially correct
26 Correct 141 ms 14200 KB Output is correct
27 Incorrect 182 ms 15352 KB Output isn't correct
28 Incorrect 224 ms 15452 KB Output isn't correct
29 Incorrect 240 ms 17600 KB Output isn't correct
30 Partially correct 320 ms 22264 KB Partially correct
31 Partially correct 181 ms 16760 KB Partially correct
32 Incorrect 181 ms 15352 KB Output isn't correct
33 Correct 136 ms 15608 KB Output is correct
34 Partially correct 211 ms 16316 KB Partially correct
35 Partially correct 158 ms 15608 KB Partially correct
36 Partially correct 218 ms 16120 KB Partially correct
37 Correct 216 ms 17528 KB Output is correct
38 Incorrect 242 ms 17364 KB Output isn't correct
39 Incorrect 286 ms 17372 KB Output isn't correct
40 Partially correct 320 ms 21468 KB Partially correct
41 Incorrect 487 ms 26428 KB Output isn't correct