제출 #444600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444600		leaked	Friends (BOI17_friends)	C++14	0 / 100	1078 ms	588 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){
            assert(false);
        }
        assert(x%2==0);x/=2;
        return m_p(x,y);
    };
//    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;pii c=get(j);
            if(ok[f] && max(c.f,c.s)<=q && __builtin_popcount(c.f)<=p){
                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: 0 / 20
• Subtask 2: 0 / 37
• Subtask 3: 0 / 12
• Subtask 4: 0 / 31