Submission #872943

#	Time	Username	Problem	Language	Result	Execution time	Memory
872943		binh192004	Geppetto (COCI15_geppetto)	C++17	80 / 80	38 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 a[21];
bool ok = 1;
void sinh(){
      int i = n;
      while (i > 0 && a[i] == 1){
            a[i] = 0;
            i--;
      }
      if (i > 0){
            a[i] = 1;
      }
      else
            ok = 0;
}
vector<int> g[21];

vector<int> vs(21);
void bexuyen67() {
      cin >> n >> m;
      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;
            g[x].push_back(y);
            g[y].push_back(x);
      }
      int ans = 0;
      while (ok){
            bool ckeck = 1;
            fill(vs.begin(), vs.end(), 0);
            for (int i = 1; i <= n; i++){
                  if (a[i]){
                        for (int v: g[i])
                              if (a[v]){
                                    ckeck = 0;
                                    break;
                              }
                  }
                  if (!ckeck)
                        break;
            }
            if (ckeck)
                ans++;
            sinh();
      }
      cout << ans;
}

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);
      int t = 1;
//      cin >> t;
      while (t--)
            bexuyen67();
}

• Subtask 1: 80 / 80