This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 1 , mod = 1e9 + 7;
vector<int> g[N] , r[N] , E(N);
inline void read(int &x){
char c;int f=1;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
x*=f;
}
main(){
int n , m , p;
read(n);
read(m);
read(p);
vector<int> x(p + 1);
for(int i = 1;i <= p;i ++){
read(x[i]);
}
if(x.back() != n){
++p;
x.emplace_back(n);
}
for(int i = 1;i <= m;i ++){
int u , v;
read(u);
read(v);
E[v]++;
g[u].emplace_back(v);
r[v].emplace_back(u);
}
queue<int> q;
for(int i = 1;i <= n;i ++){
if(E[i] == 0){
q.push(i);
}
}
vector<int> order , T(n + 1);
while((int)q.size()){
int u = q.front();
q.pop();
order.emplace_back(u);
T[u] = (int)order.size();
for(int v : g[u]){
if(--E[v] == 0){
q.push(v);
}
}
}
for(int i = 2;i <= p;i ++){
if(T[x[i]] <= T[x[i - 1]]){
cout << 0 << endl;
return 0;
}
}
int pos = 1 , L = 0;
vector<long long> dp(n + 1);
for(int i = 0;i < n;i ++){
int v = order[i];
if(v == 1){
dp[v] = 1;
}
for(int u : r[order[i]]){
dp[v] = (dp[v] + dp[u]) % mod;
}
if(v == x[pos]){
for(int j = L;j < i;j ++){
dp[order[j]] = 0;
}
L = i + 1;
++pos;
}
}
if(pos != p + 1){
cout << 0 << endl;
return 0;
}
cout << dp[x.back()] << endl;
}
Compilation message (stderr)
shell.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
12 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |