Submission #45557

#	Time	Username	Problem	Language	Result	Execution time	Memory
45557		IvanC	Shell (info1cup18_shell)	C++17	100 / 100	569 ms	41260 KiB

shell

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;
vector<int> grafo[MAXN],especiais;
int nivel[MAXN],grau[MAXN],N,M,P,marcado[MAXN],nivelatual,alvo;
ll dp[MAXN];
ll solve(int v){
	if(nivel[v] > nivelatual) return 0;
	if(nivel[v] == nivelatual && v != alvo) return 0;
	if(dp[v] != -1) return dp[v];
	ll tot = 0;
	for(int u : grafo[v]){
		tot += solve(u);
	}
	return dp[v] = (tot % MOD);
}
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%d %d %d",&N,&M,&P);
	especiais.push_back(1);
	for(int i = 1;i<=P;i++){
		int v;
		scanf("%d",&v);
		if(v != 1) especiais.push_back(v);
	}
	if(especiais.back() != N) especiais.push_back(N);
	for(int i = 1;i<=M;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		grafo[u].push_back(v);
		grau[v]++;
	}
	queue<int> bfs;
	for(int i = 1;i<=N;i++) if(grau[i] == 0) bfs.push(i);
	while(!bfs.empty()){
		int v = bfs.front();
		bfs.pop();
		for(int u : grafo[v]){
			grau[u]--;
			if(grau[u] == 0){
				nivel[u] = nivel[v] + 1;
				bfs.push(u);
			}
		}
	} 
	for(int i = 0;i+1<especiais.size();i++){
		if(nivel[especiais[i]] >= nivel[especiais[i+1]]){
			printf("0\n");
			return 0;
		}
	}
	dp[N] = 1;
	for(int i = especiais.size() - 2;i>=0;i--){
		alvo = especiais[i+1];
		nivelatual = nivel[alvo];
		solve(especiais[i]);
	}
	printf("%lld\n",dp[1]);
	return 0;
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i+1<especiais.size();i++){
                ~~~^~~~~~~~~~~~~~~~~
shell.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&M,&P);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
shell.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v);
   ~~~~~^~~~~~~~~
shell.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 20 / 20
• Subtask 4: 25 / 25