Submission #554198

#	Time	Username	Problem	Language	Result	Execution time	Memory
554198		Talha_Taki	Friends (BOI17_friends)	C++17	0 / 100	28 ms	21076 KiB

friends

#include <bits/stdc++.h>
 
using namespace std;
 
 
typedef long long ll;
typedef pair <int, int> pii;

int n, p, q, group;

vector <vector <int>> taken;
vector <vector <vector <bool>>> dp;
vector <set <int>> adj;

inline int fnc(int groupNo) {
    if (groupNo == n) return 0;
    return n % p && groupNo == n-1? n % p:p;
}

bool backtrack(int groupNo, int mask, int need) {
    if (groupNo == group) {
        assert(mask == (1<<n)-1);

        for(int i = 0; i < group; ++i) {
            for(int j = 0; j < group; ++j) {
                if (i == j) continue;
                int cnt = 0;
                for(int x : taken[i]) {
                    for(int y : taken[j]) {
                        if (adj[x].find(y) != adj[x].end()) cnt++;
                        if (cnt > q) return false;
                    }
                }
            }
        }

        cout << "home\n" << group << '\n';

        for(int i = 0; i < group; ++i) {
            cout << taken[i].size() << ' ';
            for(int x : taken[i]) cout << x << ' ';
            cout << '\n';
        }

        return true;
    }
    if (dp[groupNo][mask][need]) return false;

    for(int i = 0; i < n; ++i) {
        int bit = 1<<i;
        if ((mask & bit) != 0) continue;

        taken[groupNo].push_back(i);

        if (need == 1) {
            if (backtrack(groupNo+1, mask^bit, fnc(groupNo+1))) return true;
        }
        else if (backtrack(groupNo, mask^bit, need-1)) return true;

        taken[groupNo].pop_back();
    }

    dp[groupNo][mask][need] = true;
    return false;
}
 
int main(const int argc, const char *argv[]) {
 
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p >> q;
    group = (n + p-1) /p;

    adj.resize(n);
    taken.resize(n);
    dp.assign(group, vector <vector <bool>> (1<<n, vector <bool> (p+1, false)));

    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;

        while (x--) {
            int a;
            cin >> a;

            adj[i].insert(a);
        }
    }

    for(int i = 0; i < n; ++i) {
        for(int j = i+1; j < n; ++j) {
            bool f1 = adj[i].find(j) != adj[i].end();
            bool f2 = adj[j].find(i) != adj[j].end();

            if (f1 ^ f2) {
                cout << "detention";
                return 0;
            }
        }
    }

    if (!backtrack(0, 0, fnc(0))) {
        cout << "detention";
    }

    return 0;
}

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