Submission #554594

#	Time	Username	Problem	Language	Result	Execution time	Memory
554594		Talha_Taki	Friends (BOI17_friends)	C++17	20 / 100	218 ms	640 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 <int> friend_cnt;
vector <vector <bool>> dp, adj;


inline int fnc(int groupNo) {
    if (groupNo == n) return 0;
    return (n % p) != 0 && groupNo == group-1? n % p:p;
}
 
bool backtrack(int groupNo, int mask) {
    if (groupNo == group) {
        assert(mask == (1<<n)-1);
 
        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;

    vector <int> arr;
    for(int i = 0; i < n; ++i) {
        if (mask & (1<<i)) continue;
        arr.push_back(i);
    }

    int k = arr.size();
    int need = fnc(groupNo);
    assert(k >= need);

    vector <int> p(k, 0);
    for(int i = k-need; i < k; ++i) p[i] = 1;

    do {
        int add = 0;
        for(int i = 0; i < k; ++i) {
            if (p[i]) {
                taken[groupNo].push_back(arr[i]);
                add ^= (1<<arr[i]);
            }
        }

        bool flag = true;
        vector <int> tmp(group, 0);
        for(int i = 0; flag && i < groupNo; ++i) {
            for(int j = 0; flag && j < (int)taken[groupNo].size(); ++j) {
                for(int k = 0; flag && k < (int)taken[i].size(); ++k) {
                    int x = taken[groupNo][j];
                    int y = taken[i][k];
                    if (adj[x][y]) {
                        tmp[groupNo]++;
                        tmp[i]++;
                        if (friend_cnt[groupNo] + tmp[groupNo] > q || friend_cnt[i] + tmp[i] > q) flag = false;
                    }
                }
            }
        }
        
        if (flag) {
            for(int i = 0; i <= groupNo; ++i) {
                friend_cnt[i] += tmp[i];
            }
            if (backtrack(groupNo+1, mask ^ add)) return true;

            for(int i = 0; i <= groupNo; ++i) {
                friend_cnt[i] -= tmp[i];
            }
        }
        taken[groupNo].clear();

    } while (next_permutation(p.begin(), p.end()));


    dp[groupNo][mask] = 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.assign(n, vector <bool> (n, false));
    dp.assign(group, vector <bool> (1<<n, false));
    taken.resize(group);
    friend_cnt.assign(group, 0);

    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
 
        while (x--) {
            int a;
            cin >> a;
 
            adj[i][a] = true;
        }
    }
 
    for(int i = 0; i < n; ++i) {
        for(int j = i+1; j < n; ++j) {
            if (adj[i][j] ^ adj[j][i]) {
                cout << "detention";
                return 0;
            }
        }
    }
 
    if (!backtrack(0, 0)) {
        cout << "detention";
    }
 
    return 0;
}

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