Submission #521336

#	Time	Username	Problem	Language	Result	Execution time	Memory
521336		raid	Shell (info1cup18_shell)	C++17	100 / 100	773 ms	48228 KiB

shell

#include <iostream>
#include <iostream>
#include <vector>
#define fin cin
#define fout cout

using namespace std;

const int MAXN = 1000005;
const int MOD = 1e9 + 7;

using ll = long long;

vector<int> G[MAXN];
bool viz[MAXN];

vector<int> req_vrt;
int dp[MAXN];
vector<int> vrt;

void sort_top( int u ) {
  viz[u] = true;
  for ( auto v : G[u] ) {
    if ( !viz[v] ) {
      sort_top( v );
    }
  }
  vrt.push_back(u);
}
 
vector<pair<int, int>> rng;

int main() {
  int n, m, p, x, y;
 
  fin >> n >> m >> p;
  req_vrt.push_back(1);
  for ( int i = 0; i < p; ++i ) {
    fin >> x;
    if ( i == 0 && x == 1 ) continue;
    req_vrt.push_back(x);
  }
  if ( req_vrt.back() != n ) {
    req_vrt.push_back(n);
  }
  while ( m-- ) {  
    fin >> x >> y;
    G[y].push_back( x );
  }
  for ( int i = 1; i <= n; ++i ) {
    if ( !viz[i] ) {
      sort_top( i );
    }
  }
  int now = 0, prv = -1;
  p = req_vrt.size() - 1;
  for ( int i = 0; i < n; ++i ) {
    if ( now <= p && vrt[i] == req_vrt[now] ) {
      ++now;
      if ( prv != -1 ) rng.push_back( {prv, i} );
      prv = i;
    }
  }
  if ( now <= p ) {
    fout << 0;
    return 0;
  }
  ll res = 1;
  for ( int i = 0; i < rng.size(); ++i ) {
    dp[vrt[rng[i].first]] = 1;
    for ( int j = rng[i].first + 1; j <= rng[i].second; ++j ) {
      for ( auto v : G[vrt[j]] ) {
        dp[vrt[j]] = (dp[vrt[j]] + dp[v]) % MOD;
      }
    }
    res = (res * dp[vrt[rng[i].second]]) % MOD;
    for ( int j = rng[i].first; j <= rng[i].second; ++j ) {
      dp[vrt[j]] = 0;
    }
  }
  fout << res;
  return 0;
}

Compilation message (stderr)

shell.cpp: In function 'int main()':
shell.cpp:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for ( int i = 0; i < rng.size(); ++i ) {
      |                    ~~^~~~~~~~~~~~

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