oj.uz

Submission #689615

# Submission time Handle Problem Language Result Execution time Memory
689615 2023-01-28T21:55:45 Z tvladm2009 Shell (info1cup18_shell) C++17
100 / 100
 437 ms 78976 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 1e6 + 7;
const int M = (int) 1e9 + 7;
int a[N], special[N], degree[N], dp[N], order[N];
vector<int> in[N], out[N];

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n, m, p;
  cin >> n >> m >> p;
  for (int i = 1; i <= p; i++) {
    cin >> a[i];
    special[a[i]] = 1;
  }
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    in[y].push_back(x);
    out[x].push_back(y);
    degree[y]++;
  }
  queue<int> q;
  vector<int> depth(n + 1);
  for (int i = 1; i <= n; i++) {
    if (degree[i] == 0) {
      q.push(i);
      depth[i] = 1;
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto &v : out[u]) {
      degree[v]--;
      if (degree[v] == 0) {
        depth[v] = depth[u] + 1;
        q.push(v);
      }
    }
  }
  for (int i = 2; i <= p; i++) {
    if (depth[a[i]] <= depth[a[i - 1]]) {
      cout << "0";
      return 0;
    }
  }

  for (int i = 1; i <= n; i++) {
    order[i] = i;
  }
  sort(order + 1, order + n + 1, [&](int i, int j) {
    return depth[i] < depth[j];
  });
  int last = 0;
  for (int i = 1; i <= n; i++) {
    if (order[i] != 1) {
      if (last != 0) {
        for (auto &v : in[order[i]]) {
          if (depth[v] > depth[last] || v == last) {
            dp[order[i]] += dp[v];
            if (dp[order[i]] >= M) {
              dp[order[i]] -= M;
            }
          }
        }
      }
      if (special[order[i]]) {
        last = order[i];
      }
    } else {
      if (last == 0) {
        dp[1] = 1;
      }
      last = 1;
    }
  }
  cout << dp[n];
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 23 ms 47304 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 26 ms 47336 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 23 ms 47304 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 26 ms 47336 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct
6 Correct 23 ms 47292 KB Output is correct
7 Correct 26 ms 47848 KB Output is correct
8 Correct 28 ms 47620 KB Output is correct
9 Correct 29 ms 47928 KB Output is correct
10 Correct 28 ms 47952 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47524 KB Output is correct
2 Correct 90 ms 56932 KB Output is correct
3 Correct 90 ms 56908 KB Output is correct
4 Correct 90 ms 56888 KB Output is correct
5 Correct 66 ms 53712 KB Output is correct
6 Correct 189 ms 70848 KB Output is correct
7 Correct 186 ms 70944 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47316 KB Output is correct
2 Correct 23 ms 47304 KB Output is correct
3 Correct 23 ms 47308 KB Output is correct
4 Correct 26 ms 47336 KB Output is correct
5 Correct 23 ms 47316 KB Output is correct
6 Correct 23 ms 47292 KB Output is correct
7 Correct 26 ms 47848 KB Output is correct
8 Correct 28 ms 47620 KB Output is correct
9 Correct 29 ms 47928 KB Output is correct
10 Correct 28 ms 47952 KB Output is correct
11 Correct 23 ms 47524 KB Output is correct
12 Correct 90 ms 56932 KB Output is correct
13 Correct 90 ms 56908 KB Output is correct
14 Correct 90 ms 56888 KB Output is correct
15 Correct 66 ms 53712 KB Output is correct
16 Correct 189 ms 70848 KB Output is correct
17 Correct 186 ms 70944 KB Output is correct
18 Correct 383 ms 78976 KB Output is correct
19 Correct 404 ms 77736 KB Output is correct
20 Correct 437 ms 76848 KB Output is correct
21 Correct 125 ms 59116 KB Output is correct
22 Correct 422 ms 77964 KB Output is correct