Submission #444602

#	Time	Username	Problem	Language	Result	Execution time	Memory
444602		leaked	Friends (BOI17_friends)	C++17	20 / 100	88 ms	1100 KiB

friends

#include <bits/stdc++.h>

#define vec vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define m_p make_pair
#define pw(x) (1LL<<x)
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
auto rng=bind(uniform_int_distribution<int>(1,1000),mt19937(time(0)));
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<int,int> pii;
typedef long double ld;

signed main(){
    fast_ioi;
    int n,p,q;
    cin>>n>>p>>q;
    vec<vec<int>>g(n,vec<int>());
    for(int i=0;i<n;i++){
        int c;cin>>c;g[i].resize(c);
        for(auto &z : g[i]) cin>>z;
        sort(all(g[i]));
    }
    for(int i=0;i<n;i++){
        for(auto &z : g[i]){
            if(!binary_search(all(g[z]),i)){
                cout<<"detention";
                return 0;
            }
        }
    }
    auto get=[&](int msk){
        int x=0,y=0;
        for(int i=0;i<n;i++){
            if(pw(i)&msk){
                for(auto &z : g[i]){
                    if(pw(z)&msk) x++;
                    else y++;
                    if(x>2*q || y>q) return 0;
                }
            }
        }
        return 1;
    };
    vec<int>good(pw(n),0);
    for(int i=0;i<pw(n);i++){
        good[i]=get(i);
    }
//    cout<<get(3).f<<' '<<get(3).s<<endl;
    vec<int>ok(pw(n));
    vec<int>pr(pw(n),-1);
    ok[0]=1;
    for(int msk=1;msk<pw(n);msk++){
        for(int j=msk;j>0;j=(j-1)&msk){
            int f=msk^j;
            if(ok[f] && good[j]){
                pr[msk]=f;
                ok[msk]=1;
            }
        }
    }
    int v=pw(n)-1;
    if(!ok[v]){
        cout<<"detention";
        return 0;
    }
    vec<vec<int>>ans;
    while(v!=0){
        int x=pr[v];
        ans.pb(vec<int>());
        for(int i=0;i<n;i++){
            if(pw(i)&(v^x)) ans.back().pb(i);
        }
        v=x;
    }
    cout<<"home\n";
    cout<<sz(ans)<<endl;
    for(auto &z : ans){
        cout<<sz(z)<<' ';
        for(auto &q : z) cout<<q<<' ';
        cout<<'\n';
    }
    return 0;
}

/*
7 3
0
1
0
1
3
5
0

*/

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