Submission #95345

#TimeUsernameProblemLanguageResultExecution timeMemory
95345dalgerokShell (info1cup18_shell)C++14
100 / 100
350 ms47844 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e6 + 5, MOD = 1e9 + 7; int n, m, p, a[N], dp[N], ans[N]; vector < int > g[N]; void dfs(int v){ if(v == n){ dp[v] = ans[v] = 1; } else{ for(int to : g[v]){ if(dp[to] == 0){ dfs(to); } if(dp[to] > dp[v]){ dp[v] = dp[to]; ans[v] = ans[to]; } else if(dp[to] == dp[v]){ ans[v] += ans[to]; if(ans[v] >= MOD){ ans[v] -= MOD; } } } } if(v == a[p - dp[v] + 1]){ dp[v] += 1; } } int main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> m >> p; for(int i = 1; i <= p; i++){ cin >> a[i]; } for(int i = 1; i <= m; i++){ int x, y; cin >> x >> y; g[x].push_back(y); } dfs(1); cout << ans[1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...