Submission #447746

#	Time	Username	Problem	Language	Result	Execution time	Memory
447746		Nima_Naderi	007 (CEOI14_007)	C++14	100 / 100	304 ms	35776 KiB

007

//In the name of God
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 2e5 + 10;
const ll MXM = 6e5 + 10;
const ll INF = 1e9;
ll n, m, k, t, s[2], Src[4];
ll dis[4][MXN], Q[MXN];
vector<ll> adj[MXN];
bool vis[MXN];
void BFS(ll f, ll src){
	fill(dis[f], dis[f] + MXN, INF);
	memset(vis, 0, sizeof vis);
	ll L = 0, R = 0; Src[f] = src;
	dis[f][src] = 0, Q[R ++] = src, vis[src] = 1;
	while(L < R){
		ll u = Q[L ++];
		for(auto v : adj[u]){
			if(!vis[v]){
				dis[f][v] = dis[f][u] + 1;
				vis[v] = 1, Q[R ++] = v;
			}
		}
	}
}
inline bool in_path(ll u, ll f0, ll f1){
	ll s = Src[f0], e = Src[f1];
	return (dis[f0][u] + dis[f1][u] == dis[f0][e]);
}
ll check(ll f, ll x){//tz check
	if(dis[f][k] + x > dis[f][t]) return 1;
	if(dis[f][k] + x < dis[f][t]) return 0;
	return 2;
}
bool check(ll x){
	ll ck0 = check(0, x), ck1 = check(1, x);
	if(ck0 == 1 || ck1 == 1) return 0;
	if(ck0 == 0 || ck1 == 0) return 1;
	//return (!check(0, x)) && (!check(1, x));
	ll tz = 0, km = 0;
	for(int i = 1; i <= n; i ++){
		if(in_path(i, 2, 0) && in_path(i, 2, 1)){
			km = max(km, dis[2][i]);
		}
		if(in_path(i, 3, 0) && in_path(i, 3, 1)){
			tz = max(tz, dis[3][i]);
		}
	}
	return !(tz > km + x);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m >> k >> t >> s[0] >> s[1];
	for(int i = 1; i <= m; i ++){
		ll u, v; cin >> u >> v;
		adj[u].push_back(v), adj[v].push_back(u);
	}
	BFS(0, s[0]), BFS(1, s[1]);
	BFS(2, k), BFS(3, t);
	if(!check(0)) return cout << -1, 0;
	ll low = 0, hig = n + 1;
	while(hig - low > 1){
		ll mid = (low + hig) / 2;
		if(check(mid))	low = mid;
		else			hig = mid;
	}
	cout << low << '\n';
	return 0;
}
// I was born to be making history.
// N.N

Compilation message (stderr)

007.cpp: In function 'bool in_path(ll, ll, ll)':
007.cpp:30:5: warning: unused variable 's' [-Wunused-variable]
   30 |  ll s = Src[f0], e = Src[f1];
      |     ^

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