oj.uz

Submission #1062178

# Submission time Handle Problem Language Result Execution time Memory
1062178 2024-08-16T20:36:32 Z pera Shell (info1cup18_shell) C++17
0 / 100
 9 ms 55132 KB 
#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

shell.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main(){
      | ^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55132 KB Output is correct
2 Incorrect 9 ms 55132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55132 KB Output is correct
2 Incorrect 9 ms 55132 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 55128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55132 KB Output is correct
2 Incorrect 9 ms 55132 KB Output isn't correct
3 Halted 0 ms 0 KB -