Submission #129902

#	Time	Username	Problem	Language	Result	Execution time	Memory
129902		Abelyan	Friends (BOI17_friends)	C++17	20 / 100	69 ms	756 KiB

friends

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr firstq
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define all(v) v.begin(),v.end()
#define make_unique(v) v.erase(unique(all(v)),v.end())
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define srng mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define y1 EsiHancagorcRepa
 
const int N=17,MS=(1<<N);
const ll MOD=1e9+7;
 
int kox[N][N];
int dg[N];
bool col[MS],dp[MS];
int qan[MS],ver[MS];
int n,p,q;
 
void out(int k){
    cout<<__builtin_popcount(k)<<" ";
    FOR(i,n){
        if ((1<<i)&k)cout<<i<<" ";
    }
    cout<<endl;
}
 
int main(){
    fastio;
    srng;
    cin>>n>>p>>q;
    FOR(i,n){
        cin>>dg[i];
        FOR(j,dg[i]){
            int to;
            cin>>to;
            kox[i][to]++;
        }
    }
    //cout<<1<<endl;
    FOR(i,n){
        FOR(j,n){
            if (kox[i][j]!=kox[j][i]){
                cout<<"detention"<<endl;
                return 0;
            }
        }
    }
    //cout<<1<<endl;
    FOR(msk,(1<<n)){
        if (__builtin_popcount(msk)>p)continue;
        int qan=0;
        FOR(i,n){
            if ((1<<i)&msk){
                FOR(j,n){
                    if (!((1<<j)&msk) && kox[i][j])qan++;
                }
            }
        }
        //cout<<msk<<" "<<qan<<endl;
        if (qan<=q){
            col[msk]=true;
            //cout<<msk<<endl;
        }
    }
    //cout<<1<<endl;
    FOR(msk,(1<<n)){
        if (col[msk]){
            dp[msk]=true;
            qan[msk]=1;
            ver[msk]=msk;
            continue;
        }
        for (int s=msk;s;s=(s-1)&msk){
            if (dp[msk-s] && col[s]){
                dp[msk]=true;
                ver[msk]=s;
                qan[msk]=qan[msk-s]+1;
                break;
            }
        }
    }
    if (!dp[(1<<n)-1]){
        cout<<"detention"<<endl;
        return 0;
    }
    int cur=(1<<n)-1;
    cout<<"home\n"<<qan[cur]<<endl;
    while(cur){
        out(ver[cur]);
        cur-=ver[cur];
    }
    return 0;
}

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