제출 #1140992

#제출 시각아이디문제언어결과실행 시간메모리
1140992RufatBank (IZhO14_bank)C++20
0 / 100
712 ms327680 KiB
//Author RufatM
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<ull> vull;
typedef vector<vector<ull>> vvull;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvp;
typedef vector<pair<ll, ll>> vpll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ff first
#define ss second
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pow(x, y) static_cast<int>(pow(x, y))
#define sz(x) (int)(x).sz()
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
template<typename T> inline T sqr(T x) { return x * x; }
template<typename T> inline T modinv(T a, T mod) { return 0; }
template<class T> bool isPrime(T n) { if (n <= 1)return false;if (n <= 3)return true;if (n % 2 == 0 || n % 3 == 0)return false;for (T i = 5;i * i <= n;i += 6)if (n % i == 0 || n % (i + 2) == 0)return false;return true; }
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long LINF = 1e18 + 7;
const int MAXN = 1e5 + 5;
signed main() {
    fastio;
    int t=1;
    //cin >> t;
    while (t--) {
        int n,m;
        cin>>n>>m;
        vvi BIT[20];
        for(int i=0;i<n;i++){
            int k;
            cin>>k;
            vi a(k);
            for(int j=0;j<k;j++){
                cin>>a[j];
            }
            for(int mask=0;mask<(1<<k);mask++){
                vi subset;
                for(int j=0;j<k;j++){
                    if(mask&(1<<j)){
                        subset.pb(a[j]);
                    }
                }
                BIT[i].pb(subset);
            }
        }
        bool memo[20][1<<20];
        bool vis[20][1<<20];
        function<bool(int,vvi&,int)> backtrack=[&](int i,vvi &current,int used_mask){
            if(i==n){
                return true;
            }
            if(vis[i][used_mask]){
                return memo[i][used_mask];
            }
            vis[i][used_mask]=true;
            for(auto &subset:BIT[i]){
                int subset_mask=0;
                for(auto x:subset){
                    subset_mask|=(1<<x);
                }
                if(used_mask&subset_mask){
                    continue;
                }
                current.eb(subset);
                if(backtrack(i+1,current,used_mask|subset_mask)){
                    return memo[i][used_mask]=1;
                }
                current.ppb();
            }
            return memo[i][used_mask]=0;
        };
        vvi current;
        if(backtrack(0,current,0)){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...