oj.uz

Submission #213456

# Submission time Handle Problem Language Result Execution time Memory
213456 2020-03-25T21:01:27 Z Haunted_Cpp Shell (info1cup18_shell) C++17
100 / 100
 345 ms 44148 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;
}

int mult (int a, int b) {
  i64 res = 1LL * a * b;
  if (res >= MOD) res %= MOD;
  return res;
}

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

int target_node, dp [N];

int dfs (int node) {
  if (node == target_node) return 1;
  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;
      }
    }
  }
  memset (dp, -1, sizeof(dp));
  int res = 1;
  R0F (i, sz(especial) - 2) { 
    int current_node = especial[i];
    target_node = especial[i + 1];
    res = mult (res, dfs (current_node));
  }
  cout << res << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35584 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 22 ms 35712 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 26 ms 35584 KB Output is correct
6 Correct 27 ms 35584 KB Output is correct
7 Correct 28 ms 35840 KB Output is correct
8 Correct 26 ms 35712 KB Output is correct
9 Correct 33 ms 35832 KB Output is correct
10 Correct 30 ms 35840 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 35584 KB Output is correct
2 Correct 102 ms 38264 KB Output is correct
3 Correct 115 ms 38264 KB Output is correct
4 Correct 101 ms 38264 KB Output is correct
5 Correct 81 ms 37496 KB Output is correct
6 Correct 218 ms 42232 KB Output is correct
7 Correct 216 ms 42236 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 35584 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 22 ms 35712 KB Output is correct
4 Correct 22 ms 35584 KB Output is correct
5 Correct 26 ms 35584 KB Output is correct
6 Correct 27 ms 35584 KB Output is correct
7 Correct 28 ms 35840 KB Output is correct
8 Correct 26 ms 35712 KB Output is correct
9 Correct 33 ms 35832 KB Output is correct
10 Correct 30 ms 35840 KB Output is correct
11 Correct 28 ms 35584 KB Output is correct
12 Correct 102 ms 38264 KB Output is correct
13 Correct 115 ms 38264 KB Output is correct
14 Correct 101 ms 38264 KB Output is correct
15 Correct 81 ms 37496 KB Output is correct
16 Correct 218 ms 42232 KB Output is correct
17 Correct 216 ms 42236 KB Output is correct
18 Correct 333 ms 44148 KB Output is correct
19 Correct 345 ms 43380 KB Output is correct
20 Correct 304 ms 43000 KB Output is correct
21 Correct 131 ms 38392 KB Output is correct
22 Correct 327 ms 43768 KB Output is correct