oj.uz

Submission #554193

# Submission time Handle Problem Language Result Execution time Memory
554193 2022-04-27T22:19:44 Z Talha_Taki Friends (BOI17_friends) C++17
0 / 100
 1000 ms 340 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 1090 ms 340 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Execution timed out 1090 ms 340 KB Time limit exceeded
5 Halted 0 ms 0 KB -