Submission #872872

#	Time	Username	Problem	Language	Result	Execution time	Memory
872872		binh192004	Geppetto (COCI15_geppetto)	C++17	8 / 80	1 ms	604 KiB

geppetto

#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>

using namespace std;

typedef long double ld;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define lowbit(x) x & (-x);
#define inf 1e18
#define _inf -1e18
#define pyes cout << "YES" << endl
#define pno cout << "NO" << endl
#define inv(a) for (int& x: a) cin >> x;
#define llv(a) for (ll& x: a) cin >> x;
#define pri(a) for (int& x: a) cout << x << ' '
int const MOD = 998244353;
int const lg = 20;
int const block = 500;
// int block;
int const MAX = 3e5 + 1, N = 20;
int n, m, q, k;
bool ck[21][21];
int f[21][21];
void bexuyen67() {

      cin >> n >> m;
      vector<vector<int>> g(n + 1);
      for (int i = 0; i < m; i++){
            int x, y;
            cin >> x >> y;
            if (ck[x][y])
                  continue;
            ck[x][y] = ck[y][x] = 1;
            if (x > y)
                  swap(x, y);
            g[x].push_back(y);
      }
      int sum = 1 << n;
      for (int i = 1; i <= n; i++){
            if (g[i].empty())
                  continue;
            int sz = g[i].size();
            int after = n - i - sz;
            for (int j = 1; j <= g[i].size(); j++){
                  for (int k = 0; k <= after; k++){
                        int tol = f[sz][j]*f[after][k];
                        sum -= tol;
//                        cout << tol << '\n';
                  }
            }
      }
      cout << sum;
}

signed main() {
#ifdef binhball
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
#endif
      cin.tie(0)->sync_with_stdio(0);
      cout << fixed << setprecision(15);
      for (int i = 0; i <= N; i++){
            f[i][0] = 1;
            f[i][i] = 1;
      }
      for (int i = 2; i <= 20; i++){
            for (int j = 1; j <= i; j++){
                  f[i][j] = f[i - 1][j] + f[i - 1][j - 1];
            }
      }
      int t = 1;
//      cin >> t;
      while (t--)
            bexuyen67();
}

Compilation message (stderr)

geppetto.cpp: In function 'void bexuyen67()':
geppetto.cpp:57:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (int j = 1; j <= g[i].size(); j++){
      |                             ~~^~~~~~~~~~~~~~

• Subtask 1: 8 / 80