oj.uz

Submission #213453

# Submission time Handle Problem Language Result Execution time Memory
213453 2020-03-25T20:56:44 Z Haunted_Cpp Shell (info1cup18_shell) C++17
100 / 100
 354 ms 57204 KB 
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <string>
#include <cstring>
#include <bitset>
 
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define rsz resize
#define eb emplace_back
#define pb push_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;

const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};

const int MOD = 1e9 + 7;
const int N = 1e6 + 5;

int add (int a, int b) {
  a += b;
  if (a >= MOD) a -= MOD;
  return a;
}

vector<int> especial, deg (N), lvl (N), dp (N, -1);
vector<int> g [N];

int target_node;

int dfs (int node) {
  if (node == target_node) return dp[target_node];
  if (lvl[node] >= lvl[target_node]) return 0;
  int &res = dp[node];
  if (~res) return res;
  res = 0;
  GO (to, g[node]) {
    res = add (res, dfs (to));
  }
  return res;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int v, e, special;
  cin >> v >> e >> special;
  especial.eb(0);
  F0R (i, special) {
    int foo;
    cin >> foo;
    --foo;
    if (foo) especial.eb(foo);
  }
  if (especial.back() != v - 1) especial.eb(v - 1);
  F0R (i, e) {
    int st, et;
    cin >> st >> et;
    --st; --et;
    g[st].eb(et);
    ++deg[et];
  }
  queue<int> q;
  F0R (i, v) {
    if (!deg[i]) {
      q.push(i);
      lvl[i] = 0;
    }
  }
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    GO (to, g[node]) {
      --deg[to];
      if (!deg[to]) {
        q.push(to);
        lvl[to] = lvl[node] + 1;
      }
    }
  }
  dp[v - 1] = 1;
  R0F (i, sz(especial) - 2) {
    int current_node = especial[i];
    target_node = especial[i + 1];
    dfs (current_node);
  }
  cout << dp[0] << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 23 ms 35584 KB Output is correct
5 Correct 23 ms 35584 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 23 ms 35584 KB Output is correct
5 Correct 23 ms 35584 KB Output is correct
6 Correct 23 ms 35584 KB Output is correct
7 Correct 27 ms 35960 KB Output is correct
8 Correct 25 ms 35840 KB Output is correct
9 Correct 29 ms 36096 KB Output is correct
10 Correct 31 ms 36096 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35584 KB Output is correct
2 Correct 104 ms 38264 KB Output is correct
3 Correct 105 ms 38264 KB Output is correct
4 Correct 107 ms 42616 KB Output is correct
5 Correct 74 ms 40184 KB Output is correct
6 Correct 222 ms 52716 KB Output is correct
7 Correct 222 ms 52728 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 35584 KB Output is correct
2 Correct 23 ms 35584 KB Output is correct
3 Correct 22 ms 35456 KB Output is correct
4 Correct 23 ms 35584 KB Output is correct
5 Correct 23 ms 35584 KB Output is correct
6 Correct 23 ms 35584 KB Output is correct
7 Correct 27 ms 35960 KB Output is correct
8 Correct 25 ms 35840 KB Output is correct
9 Correct 29 ms 36096 KB Output is correct
10 Correct 31 ms 36096 KB Output is correct
11 Correct 24 ms 35584 KB Output is correct
12 Correct 104 ms 38264 KB Output is correct
13 Correct 105 ms 38264 KB Output is correct
14 Correct 107 ms 42616 KB Output is correct
15 Correct 74 ms 40184 KB Output is correct
16 Correct 222 ms 52716 KB Output is correct
17 Correct 222 ms 52728 KB Output is correct
18 Correct 338 ms 57204 KB Output is correct
19 Correct 354 ms 56312 KB Output is correct
20 Correct 330 ms 55544 KB Output is correct
21 Correct 124 ms 43768 KB Output is correct
22 Correct 325 ms 56312 KB Output is correct