oj.uz

Submission #536284

# Submission time Handle Problem Language Result Execution time Memory
536284 2022-03-12T17:32:00 Z Stickfish Friends (BOI17_friends) C++17
0 / 100
 1 ms 376 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 376 KB EMERGENCY!!! contestant found solution when jury didn't
2 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 340 KB EMERGENCY!!! contestant found solution when jury didn't
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 340 KB EMERGENCY!!! contestant found solution when jury didn't
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Failed 1 ms 376 KB EMERGENCY!!! contestant found solution when jury didn't
2 Halted 0 ms 0 KB -