Submission #557876

#	Time	Username	Problem	Language	Result	Execution time	Memory
557876		fatemetmhr	Friends (BOI17_friends)	C++17	20 / 100	1089 ms	360 KiB

friends

// ~Be name khoda~ //
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second
 
const int maxn5 = 200 + 10;

int n, p, q;
bool dp[1 << 20];
int par[1 << 20], av[maxn5];
vector <int> out, adj[maxn5];
bool ed[maxn5][maxn5];
 

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> n >> p >> q;

    for(int i = 0; i < n; i++){
        int l; cin >> l;
        while(l--){
            int a; cin >> a;
            adj[i].pb(a);
            ed[i][a] = true;
        }
    }
    for(int i = 0; i < n; i++) for(auto u : adj[i])
        if(!ed[u][i])
            return cout << "detention" << endl, 0;
    dp[0] = true;
    for(int mask = 1; mask < (1 << n); mask++){
        int pt = 0;
        for(int i = 0; i < n; i++) if((mask >> i)&1)
            av[pt++] = i;
        for(int s = 0; s < (1 << (pt - 1)); s++) if(__builtin_popcount(s) < p){
            int sub = s + (1 << (pt - 1));
            int sum = 0;
            for(int i = 0; i < pt; i++) if((sub >> i)&1){
                for(auto u : adj[av[i]]) if(1 ^ ((sub >> u)&1))
                    sum++; 
            }
            if(sum <= q && dp[mask ^ sub]){
                dp[mask] = true;
                par[mask] = sub;
            }
        }
    }
    if(!dp[(1 << n) - 1])
        return cout << "detention" << endl, 0;
    cout << "home" << endl;
    int mask = (1 << n) - 1;
    while(mask){
        out.pb(par[mask]);
        mask ^= par[mask];
    }
    cout << out.size() << endl;
    for(auto mask : out){
        cout << __builtin_popcount(mask) << ' ';
        for(int i = 0; i < n; i++) if((mask >> i)&1)
            cout << i << ' ';
        cout << endl;
    }
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 37
• Subtask 3: 0 / 12
• Subtask 4: 0 / 31