Submission #292252

#	Time	Username	Problem	Language	Result	Execution time	Memory
292252		davooddkareshki	007 (CEOI14_007)	C++17	100 / 100	417 ms	45668 KiB

007

#include<bits/stdc++.h>

using namespace std;
 
#define int long long
#define F first 
#define S second 
#define pii pair<int,int> 
#define mpr make_pair

typedef long long ll;

const int maxn = 2e5+10;
const int mod = 1e9+7;
const ll inf = 1e18+10;

int n, m, k, t, a, b;
vector<int> g[maxn], H[maxn];

bool mark[maxn];
int dis[maxn];
vector<int> ve;

void bfs()
{
	queue<int> q;
	q.push(a); q.push(b);
	dis[b] = dis[a] = 0;
	mark[b] = mark[a] = 1;	
	
	while(q.size())
	{
		int v = q.front();
		q.pop();
		ve.push_back(v);
		for(auto u : g[v])
			if(!mark[u])
			{
				mark[u] = 1;
				dis[u] = dis[v] + 1;
				q.push(u);		
			}
	}
}

bool isa[maxn], isb[maxn];
void dfs(int v, char tp)
{	
	if(tp == 'a') isa[v] = 1;
	if(tp == 'b') isb[v] = 1;
	mark[v] = 1;
	for(auto u : H[v])
		if(!mark[u]) dfs(u,tp);
}

int mn[maxn];
signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);	

	cin>> n >> m >> k >> t >> a >> b;
	for(int i = 1, u, v; i <= m; i++)
	{
		cin>> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs();

	for(int v = 1; v <= n; v++) 
		for(auto u : g[v])
			if(dis[u] == dis[v]+1)
				H[v].push_back(u);	
	memset(mark, 0, sizeof mark); dfs(a,'a');
	memset(mark, 0, sizeof mark); dfs(b,'b');
	
	for(int v = 1; v <= n; v++)
		if(isa[v] && isb[v]) mn[v] = dis[v];
		else mn[v] = inf;
	
	for(auto v : ve)
		for(auto u : H[v])
			mn[u] = min(mn[u],mn[v]);
	
	if(dis[t] < dis[k]) return cout<< -1, 0;
	if(mn[t] == inf && mn[k] == inf)
	{
		if((isa[t] && isa[k]) || (isb[t] && isb[k])) cout<< dis[t] - dis[k];
		else                                         cout<< dis[t] - dis[k] - 1;
	}
	else 
	{
		if(mn[t] < mn[k]) cout<< dis[t] - dis[k] - 1;
		else               cout<< dis[t] - dis[k];
	}	
}

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