| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 110791 |
2019-05-12T08:46:35 Z |
ckodser |
007 (CEOI14_007) |
C++14 |
|
377 ms |
19320 KB |
#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;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 4 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 5 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 6 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 7 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 10 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 11 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 12 |
Correct |
6 ms |
5376 KB |
Output is correct |
| 13 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 14 |
Correct |
6 ms |
5248 KB |
Output is correct |
| 15 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 16 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 17 |
Correct |
9 ms |
5248 KB |
Output is correct |
| 18 |
Correct |
8 ms |
5376 KB |
Output is correct |
| 19 |
Correct |
8 ms |
5248 KB |
Output is correct |
| 20 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 21 |
Correct |
8 ms |
5376 KB |
Output is correct |
| 22 |
Correct |
7 ms |
5248 KB |
Output is correct |
| 23 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 24 |
Correct |
8 ms |
5376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
7648 KB |
Output is correct |
| 2 |
Correct |
68 ms |
8568 KB |
Output is correct |
| 3 |
Correct |
41 ms |
7800 KB |
Output is correct |
| 4 |
Correct |
66 ms |
8696 KB |
Output is correct |
| 5 |
Correct |
40 ms |
7572 KB |
Output is correct |
| 6 |
Correct |
36 ms |
7800 KB |
Output is correct |
| 7 |
Correct |
41 ms |
8084 KB |
Output is correct |
| 8 |
Correct |
44 ms |
8184 KB |
Output is correct |
| 9 |
Correct |
55 ms |
8572 KB |
Output is correct |
| 10 |
Correct |
215 ms |
13896 KB |
Output is correct |
| 11 |
Correct |
78 ms |
10104 KB |
Output is correct |
| 12 |
Correct |
104 ms |
11164 KB |
Output is correct |
| 13 |
Correct |
87 ms |
10360 KB |
Output is correct |
| 14 |
Correct |
73 ms |
9816 KB |
Output is correct |
| 15 |
Correct |
125 ms |
11260 KB |
Output is correct |
| 16 |
Correct |
107 ms |
11512 KB |
Output is correct |
| 17 |
Correct |
99 ms |
10956 KB |
Output is correct |
| 18 |
Correct |
108 ms |
10836 KB |
Output is correct |
| 19 |
Correct |
158 ms |
12168 KB |
Output is correct |
| 20 |
Correct |
273 ms |
15704 KB |
Output is correct |
| 21 |
Correct |
231 ms |
13432 KB |
Output is correct |
| 22 |
Correct |
139 ms |
12280 KB |
Output is correct |
| 23 |
Correct |
169 ms |
13224 KB |
Output is correct |
| 24 |
Correct |
153 ms |
13064 KB |
Output is correct |
| 25 |
Correct |
132 ms |
12744 KB |
Output is correct |
| 26 |
Correct |
131 ms |
12408 KB |
Output is correct |
| 27 |
Correct |
144 ms |
13376 KB |
Output is correct |
| 28 |
Correct |
170 ms |
13304 KB |
Output is correct |
| 29 |
Correct |
223 ms |
13724 KB |
Output is correct |
| 30 |
Correct |
266 ms |
16632 KB |
Output is correct |
| 31 |
Correct |
201 ms |
14500 KB |
Output is correct |
| 32 |
Correct |
180 ms |
13320 KB |
Output is correct |
| 33 |
Correct |
147 ms |
13504 KB |
Output is correct |
| 34 |
Correct |
255 ms |
13836 KB |
Output is correct |
| 35 |
Correct |
255 ms |
13560 KB |
Output is correct |
| 36 |
Correct |
192 ms |
13944 KB |
Output is correct |
| 37 |
Correct |
243 ms |
14968 KB |
Output is correct |
| 38 |
Correct |
212 ms |
14712 KB |
Output is correct |
| 39 |
Correct |
273 ms |
14820 KB |
Output is correct |
| 40 |
Correct |
285 ms |
17016 KB |
Output is correct |
| 41 |
Correct |
377 ms |
19320 KB |
Output is correct |
