Submission #1062170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062170		pera	Shell (info1cup18_shell)	C++17	0 / 100	12 ms	55340 KiB

shell

#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);
   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;
      }
   }
   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(){
      | ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 45
• Subtask 3: 0 / 20
• Subtask 4: 0 / 25