oj.uz

Submission #204993

# Submission time Handle Problem Language Result Execution time Memory
204993 2020-02-27T16:31:40 Z Haunted_Cpp Shell (info1cup18_shell) C++17
55 / 100
 1000 ms 38904 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cassert>
#include <bitset>
using namespace std;
 
#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 f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
 
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};

void setIO(string nome) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen ((nome + ".in").c_str(), "r", stdin);
  freopen ((nome + ".out").c_str(), "w", stdout);
}

const int N = 2e3 + 5;
const int M = 2e3 + 5;
const int MOD = 1e9 + 7;

int n, m, k, streak [N];
i64 dp [N][M];
vvi g (N);

void add (i64 &a, i64 b) {
  a += b;
  a %= MOD;
}

i64 solve (int node, int match) {
  if (node == n - 1) return (match == k);
  i64 &res = dp[node][match];
  if (~res) return res;
  res = 0;
  int target = (match < k ? streak[match] : -1); 
  GO (to, g[node]) add (res, solve (to, match + (to == target)));
  return res;
} 

int main () {
  ios_base::sync_with_stdio(0); 
  cin.tie(0);
  cin >> n >> m >> k;
  assert (n < N);
  memset (dp, -1, sizeof(dp));
  F0R (i, k) {
    cin >> streak[i];
    --streak[i];
  }
  F0R (i, m) {
    int st, et;
    cin >> st >> et;
    --st; --et;
    g[st].eb(et);
  } 
  cout << solve (0, streak[0] == 0 ? 1 : 0) << '\n';
  return 0;
}

Compilation message

shell.cpp: In function 'void setIO(std::__cxx11::string)':
shell.cpp:39:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ((nome + ".in").c_str(), "r", stdin);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
shell.cpp:40:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ((nome + ".out").c_str(), "w", stdout);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31864 KB Output is correct
2 Correct 22 ms 31864 KB Output is correct
3 Correct 22 ms 31864 KB Output is correct
4 Correct 25 ms 31832 KB Output is correct
5 Correct 22 ms 31864 KB Output is correct
6 Correct 22 ms 31864 KB Output is correct
7 Correct 67 ms 31996 KB Output is correct
8 Correct 54 ms 31992 KB Output is correct
9 Correct 29 ms 32376 KB Output is correct
10 Correct 35 ms 32376 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 31864 KB Output is correct
2 Execution timed out 1041 ms 38904 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 31864 KB Output is correct
2 Correct 22 ms 31864 KB Output is correct
3 Correct 22 ms 31864 KB Output is correct
4 Correct 25 ms 31832 KB Output is correct
5 Correct 22 ms 31864 KB Output is correct
6 Correct 22 ms 31864 KB Output is correct
7 Correct 67 ms 31996 KB Output is correct
8 Correct 54 ms 31992 KB Output is correct
9 Correct 29 ms 32376 KB Output is correct
10 Correct 35 ms 32376 KB Output is correct
11 Correct 26 ms 31864 KB Output is correct
12 Execution timed out 1041 ms 38904 KB Time limit exceeded
13 Halted 0 ms 0 KB -