Submission #383390

#TimeUsernameProblemLanguageResultExecution timeMemory
383390Leonardo_PaesBitaro’s Party (JOI18_bitaro)C++17
0 / 100
3 ms3052 KiB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int ans[maxn];
bool chegay[maxn];
vector<int> grafo[maxn];

void dfs(int u, int x){
	if(u == x){
		ans[u] = 0;
		chegay[u] = 1;
		return;
	}
	bool ok = 0;
	for(int v : grafo[u]){
		if(chegay[v]) ans[u] = max(ans[u], ans[v]);
		if(v <= x) ok = 1;
		if(ans[v] != -1 or v > x) continue;
		dfs(v, x);
		chegay[u] |= chegay[v];
		if(chegay[v]) ans[u] = max(ans[u], ans[v]);
	}
	if(ok) ++ans[u];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, m, q;
	cin >> n >> m >> q;
	for(int i=1; i<=m; i++){
		int u, v;
		cin >> u >> v;
		grafo[u].push_back(v);
	}
	int t, y;
	cin >> t >> y;
	vector<bool> mark(n+1, 1);
	for(int i=0; i<y; i++){
		int x;
		cin >> x;
		mark[x] = 0;
	}
	memset(ans, -1, sizeof ans);
	for(int i=t; i>=1; i--){
		dfs(i, t);
	}
	int tfg = 0;
	for(int i=1; i<=n; i++){
		if(mark[i]) tfg = max(tfg, ans[i]);
	}
	cout << tfg << "\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...