oj.uz

Submission #554605

# Submission time Handle Problem Language Result Execution time Memory
554605 2022-04-28T22:18:33 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 <int> friend_cnt;
vector <bool> vis;
vector <vector <bool>> 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) {
    if (groupNo == group) { 
        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;
    }
 
    vector <int> arr;
    for(int i = 0; i < n; ++i) {
        if (vis[i]) continue;
        arr.push_back(i);
    }
 
    int k = arr.size();
    int need = fnc(groupNo);
 
    vector <int> p(k, 0);
    for(int i = k-need; i < k; ++i) p[i] = 1;
 
    do {
        for(int i = 0; i < k; ++i) {
            if (p[i]) {
                taken[groupNo].push_back(arr[i]);
            }
        }
        for(int x : taken[groupNo]) vis[x] = true;
 
        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)) return true;
 
            for(int i = 0; i <= groupNo; ++i) {
                friend_cnt[i] -= tmp[i];
            }
        }

        for(int x : taken[groupNo]) vis[x] = false;
        taken[groupNo].clear();
 
    } while (next_permutation(p.begin(), p.end()));
 
    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));
    vis.assign(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)) {
        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 1 ms 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Execution timed out 1096 ms 316 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 Execution timed out 1092 ms 340 KB Time limit exceeded
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 Execution timed out 1092 ms 340 KB Time limit exceeded
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 316 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Execution timed out 1096 ms 316 KB Time limit exceeded
5 Halted 0 ms 0 KB -