Submission #536284

#	Time	Username	Problem	Language	Result	Execution time	Memory
536284		Stickfish	Friends (BOI17_friends)	C++17	0 / 100	1 ms	376 KiB

friends

#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int MAXN = 2501;
vector<int> edg[MAXN];


signed main() {
    int n, p, q;
    cin >> n >> p >> q;
    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;
        edg[i].resize(m);
        for (int j = 0; j < m; ++j)
            cin >> edg[i][j];
    }
    if (n <= 16) {
        bitset<1 << 16> good;
        for (int m = 0; m < (1 << n); ++m) {
            bitset<16> bs = m;
            if (bs.count() > p)
                continue;
            int cnt = 0;
            for (int i = bs._Find_first(); i < n; i = bs._Find_next(i)) {
                for (auto u : edg[i]) {
                    if (!bs[u])
                        ++cnt;
                }
            }
            good[m] = (cnt <= q);
            //for (int i = 0; i < n; ++i)
                //cout << bs[i];
            //cout << " : " << good[m] << endl;
        }
        bitset<1 << 16> ans;
        ans[0] = 1;
        for (int m = 1; m < (1 << n); ++m) {
            for (int t = m; t > 0; t = (t - 1) & m) {
                if (good[t] && ans[m - t]) {
                    ans[m] = 1;
                    break;
                }
            }
        }
        if (!ans[(1 << n) - 1]) {
            cout << "detention\n";
            return 0;
        }
        cout << "home\n";
        vector<int> v;
        int m = (1 << n) - 1;
        while (m > 0) {
            int s = m;
            while (s > 0) {
                if (good[s] && ans[m - s]) {
                    v.push_back(s);
                    m -= s;
                    break;
                }
                s = (s - 1) & m;
            }
        }
        cout << v.size() << endl;
        for (auto s : v) {
            bitset<16> bs = s;
            cout << bs.count() << ' ';
            for (int i = bs._Find_first(); i < n; i = bs._Find_next(i))
                cout << i << ' ';
            cout << '\n';
        }
    } else if (q <= 2) {

    }
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:24:28: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |             if (bs.count() > p)
      |                 ~~~~~~~~~~~^~~

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