1320B - Navigation System - CodeForces Solution

#include<bits/stdc++.h>
#include <chrono>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
using namespace std::chrono;

#define speedup ios_base::sync_with_stdio(false);cin.tie(NULL);
ll gcd(ll a, ll b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}
namespace modop {
	ll madd(ll a, ll b) {
		return (a + b) % mod;
	}
	ll msub(ll a, ll b) {
		return (((a - b) % mod) + mod) % mod;
	}
	ll mmul(ll a, ll b) {
		return ((a % mod) * (b % mod)) % mod;
	}
	ll mpow(ll base, ll exp) {
		ll res = 1;
		while (exp) {
			if (exp % 2 == 1) {
				res = (res * base) % mod;
			}
			exp >>= 1;
			base = (base * base) % mod;
		}
		return res;
	}
	ll minv(ll base) {
		return mpow(base, mod - 2);
	}
	ll mdiv(ll a, ll b) {
		return mmul(a, minv(b));
	}
	const ll FACTORIAL_SIZE = 1.1e6;
	ll fact[FACTORIAL_SIZE], ifact[FACTORIAL_SIZE];
	void gen_factorial(ll n) {
		fact[0] = fact[1] = ifact[0] = ifact[1] = 1;

		for (ll i = 2; i <= n; i++) {
			fact[i] = (i * fact[i - 1]) % mod;
		}
		ifact[n] = minv(fact[n]);
		for (ll i = n - 1; i >= 2; i--) {
			ifact[i] = ((i + 1) * ifact[i + 1]) % mod;
		}
	}
	ll nck(ll n, ll k) {

		if (k == 0) {
			return 1;
		}
		ll den = (ifact[k] * ifact[n - k]) % mod;
		return (den * fact[n]) % mod;
	}
}
using namespace modop;
//bfs from end node
vector<int> g[200005];
vector<bool> vis(200005);
vector<int> rg[200005];
vector<int> dis(200005);
vector<bool> maxi(200005);
vector<bool> mini(200005);
vector<int> ct(200005);
set<int> forbidden;
void bfs(int start) {
	vis[start] = 1;
	queue<int> q;
	q.push(start);
	dis[start] = 0;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (auto node : rg[now]) {
			if (!vis[node]) {
				dis[node] = dis[now] + 1;
				vis[node] = 1;
				q.push(node);
				ct[node]++;
			}
			else {
				if (dis[now] + 1 == (dis[node])) {
					ct[node]++;
				}
			}
		}
	}
}
int main() {
	speedup;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		rg[y].push_back(x);
	}
	
	int k;
	cin >> k;
	vector<int> path(k + 1);
	for (int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		forbidden.insert(x);
		path[i] = x;
	}
	
	bfs(path[k]);
	int maxc = 0;
	int minc = 0;
	for (int i = 2; i <= k; i++) {
		if (dis[path[i]] == (dis[path[i - 1]] - 1)) {
			if (ct[path[i - 1]] > 1) {
				maxc++;
			}
		}
		else {
			minc++;
			maxc++;
		}
	}
	cout << minc << " " << maxc << endl;
}