oj.uz

Submission #554594

# Submission time Handle Problem Language Result Execution time Memory
554594 2022-04-28T21:07:55 Z Talha_Taki Friends (BOI17_friends) C++17
20 / 100
 218 ms 640 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 <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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 16 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 218 ms 348 KB Output is correct
7 Correct 182 ms 364 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Runtime error 1 ms 640 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Runtime error 1 ms 640 KB Execution killed with signal 11
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 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 16 ms 352 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 218 ms 348 KB Output is correct
7 Correct 182 ms 364 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Runtime error 1 ms 640 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -