Submission #915813

#TimeUsernameProblemLanguageResultExecution timeMemory
915813andrei_iorgulescuShell (info1cup18_shell)C++14
100 / 100
207 ms58236 KiB
#include <bits/stdc++.h> using namespace std; #define int long long int modulo = 1e9 + 7; int n,m,p,drum[1000005]; vector<int>g[1000005]; int dp[1000005],cine[1000005]; bool viz[1000005]; void dfs(int nod) { if (nod == n) dp[nod] = 1,cine[nod] = p,viz[nod] = true; else { viz[nod] = true; cine[nod] = 1e9; if (g[nod].size() == 0) return; for (auto vecin : g[nod]) if (!viz[vecin]) dfs(vecin); int mn = 1e9; for (auto vecin : g[nod]) mn = min(mn,cine[vecin]); cine[nod] = mn; if (mn < 1e9 and drum[mn - 1] == nod) cine[nod]--; for (auto vecin : g[nod]) if (cine[vecin] == mn) dp[nod] += dp[vecin]; dp[nod] %= modulo; //cout << nod << ' ' << cine[nod] << ' ' << dp[nod] << endl; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> p; for (int i = 1; i <= p; i++) cin >> drum[i]; if (drum[p] != n) drum[++p] = n; for (int i = 1; i <= m; i++) { int x,y; cin >> x >> y; g[x].push_back(y); } dfs(1); if (cine[1] == 1) cout << dp[1]; else cout << 0; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...