oj.uz

Submission #920497

# Submission time Handle Problem Language Result Execution time Memory
920497 2024-02-02T15:45:12 Z zeta7532 Friends (BOI17_friends) C++17
20 / 100
 67 ms 536 KB 
#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;
        }
    }
    rep(i,N){
        rep(j,N){
            if(A[i][j]!=A[j][i]){
                cout << "detention" << endl;
                return 0;
            }
        }
    }
    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++;
            if(bit&(1<<i)) continue;
            rep(j,N){
                if(bit&(1<<j)) if(A[i][j]) cnt++;
            }
        }
        if(people<=P&&cnt<=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

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++)
......
   77 |         rep(i,ans.size()){
      |             ~~~~~~~~~~~~      
friends.cpp:77:9: note: in expansion of macro 'rep'
   77 |         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++)
......
   81 |             rep(j,ANS.size()) cout << ANS[j] << " ";
      |                 ~~~~~~~~~~~~  
friends.cpp:81:13: note: in expansion of macro 'rep'
   81 |             rep(j,ANS.size()) cout << ANS[j] << " ";
      |             ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 30 ms 496 KB Output is correct
5 Correct 67 ms 348 KB Output is correct
6 Correct 65 ms 348 KB Output is correct
7 Correct 66 ms 536 KB Output is correct
8 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 6 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 6 ms 344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 30 ms 496 KB Output is correct
5 Correct 67 ms 348 KB Output is correct
6 Correct 65 ms 348 KB Output is correct
7 Correct 66 ms 536 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 6 ms 344 KB Output isn't correct
11 Halted 0 ms 0 KB -