Submission #1062577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062577		sleepntsheep	Amusement Park (CEOI19_amusementpark)	C++17	0 / 100	1 ms	348 KiB

amusementpark

#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};
}
ii prod(ii a, ii b) {
  return {(a.first * 1ll * a.second % M + b.first * 1ll * a.second % M) % M * 1ll * bpow(a.second * 1ll * b.second % M, M - 2) % M,
    a.second * 1ll * b.second % M};
}

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, 1}));
    }
  }

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

Compilation message (stderr)

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37