Submission #718084

#	Time	Username	Problem	Language	Result	Execution time	Memory
718084		Johann	Friends (BOI17_friends)	C++14	20 / 100	22 ms	468 KiB

friends

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

int P,Q,N;
bool GROUP[1<<17] = { false };
bool DP[1<<17] = { false };
int DPRec[1<<17] = { -1 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, p, q;
    cin >> n >> p >> q;
    N = n; P = p; Q = q;

    vvi adj(n);
    F0R(i,n) {
        int m,s;
        cin >> m;
        adj[i].resize(m);
        F0R(j,m) {
            cin >> s;
            adj[i][j] = s;
        }
        sort(all(adj[i]));
    }
    // every friendship mutual?
    F0R(i,n) {
        for (int j : adj[i]) {
            if (!binary_search(all(adj[j]), i)) {
                cout << "detention\n";
                return 0;
            }
        }
    }
    // bruteforce rest.
    F0R(i,1<<n){
        if (__builtin_popcount(i) > p) continue;
        int out = 0;
        F0R(v,n) {
            if (!(i & (1<<v))) continue;
            for (int u : adj[v]) {
                if (!(i & (1<<u))) ++out;
            }
        }
        if (out <= q) {
            GROUP[i] = true;
            DP[i] = true;
            DPRec[i] = 0;
        }
    }

    F0R(s,1<<n) {
        if (!DP[s]) continue;
        int T = ((1<<n)-1) ^ s;
        for (int t = T; t > 0; t = T & (t-1)) {
            if (GROUP[t]) {
                DP[s | t] = true;
                DPRec[s | t] = s;
            }
        }
    }

    if (DP[(1<<n) - 1]) {
        cout << "home\n";
        vvi ans;
        int s = (1<<n) - 1;
        while (s > 0) {
            int t = DPRec[s] ^ s;
            ans.emplace_back();
            F0R(v,n) {
                if (t & (1<<v)) ans.back().push_back(v);
            }
            s = s ^ t;
        }
        cout << sz(ans) << "\n";
        for (vi xx : ans) {
            cout << sz(xx);
            for (int x : xx) cout << " " << x;
            cout << "\n";
        }
    } else cout << "detention\n";
}

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