Submission #920487

#	Time	Username	Problem	Language	Result	Execution time	Memory
920487		zeta7532	Friends (BOI17_friends)	C++17	0 / 100	5 ms	348 KiB

friends

#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = int;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

int main() {
    ll N,P,Q;
    cin >> N >> P >> Q;
    bool A[N][N];
    rep(i,N) rep(j,N) A[i][j]=false;
    rep(i,N){
        ll x;
        cin >> x;
        rep(j,x){
            ll y;
            cin >> y;
            A[i][y]=true;
        }
    }
    bool S[1<<N];
    rep(bit,1<<N){
        S[bit]=false;
        ll people=0;
        ll cnt=0;
        rep(i,N){
            if(bit&(1<<i)) people++;
            rep(j,N){
                if(bit&(1<<i)) if(bit&(1<<j)) if(A[i][j]) cnt++;
            }
        }
        if(people<=P&&cnt>=2*Q) S[bit]=true;
    }
    bool dp[1<<N];
    rep(bit,1<<N) dp[bit]=false;
    dp[0]=true;
    for(ll bit=1;bit<(1<<N);bit++){
        for(ll T=bit;T>=0;T--){
            T&=bit;
            if(T==0) continue;
            if(S[T]) if(dp[bit-T]) dp[bit]=true;
        }
    }
    if(dp[(1<<N)-1]){
        cout << "home" << endl;
        vector<ll> ans;
        ll bit=(1<<N)-1;
        while(1){
            for(ll T=bit;T>=0;T--){
                T&=bit;
                if(T==bit) continue;
                if(dp[T]&&S[bit-T]){
                    ans.push_back(bit-T);
                    bit=T;
                    break;
                }
            }
            if(bit==0) break;
        }
        cout << ans.size() << endl;
        rep(i,ans.size()){
            vector<ll> ANS;
            rep(j,N) if(ans[i]&(1<<j)) ANS.push_back(j);
            cout << ANS.size() << " ";
            rep(j,ANS.size()) cout << ANS[j] << " ";
            cout << endl;
        }
    }else{
        cout << "detention" << endl;
    }
    return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:10:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define rep(i,n) for(ll i=0;i<n;i++)
......
   68 |         rep(i,ans.size()){
      |             ~~~~~~~~~~~~      
friends.cpp:68:9: note: in expansion of macro 'rep'
   68 |         rep(i,ans.size()){
      |         ^~~
friends.cpp:10:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define rep(i,n) for(ll i=0;i<n;i++)
......
   72 |             rep(j,ANS.size()) cout << ANS[j] << " ";
      |                 ~~~~~~~~~~~~  
friends.cpp:72:13: note: in expansion of macro 'rep'
   72 |             rep(j,ANS.size()) cout << ANS[j] << " ";
      |             ^~~

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