#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 11;
vector<int> G[MAXN];
bool vis[MAXN];
bool zero = true;
vector<int> tp;
int n, m, p;
void dfs(int v){
vis[v] = true;
if(v == n) zero = false;
for(auto i : G[v]){
if(!vis[i]) dfs(i);
}
tp.push_back(v);
}
int dp[MAXN], to[MAXN];
int32_t main(){
cin.tie(0); cout.tie(0)->sync_with_stdio(false);
cin >> n >> m >> p;
vector<int> v;
for(int i = 0; i < p; i++){
int k; cin >> k; if(k == 1) continue; v.push_back(k);
}
vector<pair<int, int>> vp, vp2;
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
vp.push_back({u, v});
G[u].push_back(v);
}
dfs(1);
reverse(tp.begin(), tp.end());
// for(auto i : tp) cout << i << ' '; cout << endl;
while(tp.size() && tp.back() != n) tp.pop_back();
if(zero || tp.empty()) { cout << 0 << endl; return 0; }
for(int i = 0; i < tp.size(); i++){
to[tp[i]] = i + 1;
}
vector<int> d; d.push_back(0); d.push_back(1);
for(int i = 0; i < p; i++){
if(to[v[i]] == 0){
cout << 0 << endl; return 0;
}
if(i != 0 && to[v[i - 1]] > to[v[i]]){
cout << 0 << endl; return 0;
}
d.push_back(to[v[i]]);
}
for(auto i : vp){
if(to[i.fi] == 0 || to[i.se] == 0) continue;
int f = to[i.fi], t = to[i.se];
if(t > *upper_bound(d.begin(), d.end(), f)) continue;
vp2.push_back({f, t});
// cout << f << " -> " << t << endl;
}
sort(vp2.begin(), vp2.end());
dp[1] = 1;
for(auto i : vp2){
dp[i.se] = (dp[i.fi] + dp[i.se]) % MOD;
}
cout << dp[(int) tp.size() - 1] << endl;
}
Compilation message
shell.cpp: In function 'int32_t main()':
shell.cpp:43:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i = 0; i < tp.size(); i++){
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
