oj.uz

Submission #1062578

# Submission time Handle Problem Language Result Execution time Memory
1062578 2024-08-17T08:48:24 Z sleepntsheep Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 0 ms 348 KB 
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <unordered_set>
#include <vector>

using namespace std;
using ll = long long;
using ii = pair<int, int>;

const ll M = 998244353;

vector<int> g[22];
int n, m, a[999], b[999], p[22], q[22]; 
ii dp[1<<22];

ll bpow(ll a, ll b) {
  if (!b) return 1;
  ll r = bpow(a, b / 2);
  if (b & 1) return r * r % M * a % M;
  return r * r % M;
}

ii add(ii a, ii b) {
  return {(a.first * 1ll * a.second % M + b.first * 1ll * b.second % M) % M * 1ll * bpow((a.second + b.second) % M, M - 2) % M
    , (a.second + b.second) % M};
}
ii prod(ii a, ll b) {
  return {(a.first * 1ll * a.second % M + b * a.second % M) % M * 1ll * bpow(a.second, M - 2) % M,
    a.second};
}

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; ++i)
    scanf("%d%d", a+i, b+i), --a[i], --b[i], g[a[i]].push_back(b[i]);

  dp[0] = {0, 1};
  for (int j = 0; j < (1 << n); ++j) {
    for (int i = 0; i < n; ++i) if (j & (1 << i)) {
      int k = j & ~(1 << i), c {};
      for (int v : g[i]) c += (k >> v) & 1;
      dp[j] = add(dp[j], prod(dp[k], c));
    }
  }

  printf("%lld", dp[(1 << n) - 1].first * 1ll * dp[(1 << n) - 1].second % M);
}

Compilation message

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
amusementpark.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     scanf("%d%d", a+i, b+i), --a[i], --b[i], g[a[i]].push_back(b[i]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -