Submission #1062178

#TimeUsernameProblemLanguageResultExecution timeMemory
1062178peraShell (info1cup18_shell)C++17
0 / 100
9 ms55132 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...