Submission #554193

#	Time	Username	Problem	Language	Result	Execution time	Memory
554193		Talha_Taki	Friends (BOI17_friends)	C++17	0 / 100	1090 ms	340 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 <bool>> dp;
vector <set <int>> adj;

bool backtrack(int groupNo, int mask) {
    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]) return false;

    int need = (n % p && groupNo == n-1? n % p:p);
    for(int i = 1; i < (1<<n); ++i) {
        if ((mask & i) != 0 || __builtin_popcount(i) != need) continue;
        
        mask ^= i;
        for(int j = 0; j < n; ++j) {
            if (i & (1<<j)) {
                taken[groupNo].push_back(j);
            }
        }

        if (backtrack(groupNo+1, mask)) return true;

        mask ^= i;
        taken[groupNo].clear();
    }

    return dp[groupNo][mask] = 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 <bool> (1<<n, 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)) {
        cout << "detention";
    }

    return 0;
}

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