oj.uz

Submission #718084

# Submission time Handle Problem Language Result Execution time Memory
718084 2023-04-03T09:54:36 Z Johann Friends (BOI17_friends) C++14
20 / 100
 22 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define vb vector<bool>
#define vi vector<int>
#define vvi vector<vi>
#define F0R(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

int P,Q,N;
bool GROUP[1<<17] = { false };
bool DP[1<<17] = { false };
int DPRec[1<<17] = { -1 };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, p, q;
    cin >> n >> p >> q;
    N = n; P = p; Q = q;

    vvi adj(n);
    F0R(i,n) {
        int m,s;
        cin >> m;
        adj[i].resize(m);
        F0R(j,m) {
            cin >> s;
            adj[i][j] = s;
        }
        sort(all(adj[i]));
    }
    // every friendship mutual?
    F0R(i,n) {
        for (int j : adj[i]) {
            if (!binary_search(all(adj[j]), i)) {
                cout << "detention\n";
                return 0;
            }
        }
    }
    // bruteforce rest.
    F0R(i,1<<n){
        if (__builtin_popcount(i) > p) continue;
        int out = 0;
        F0R(v,n) {
            if (!(i & (1<<v))) continue;
            for (int u : adj[v]) {
                if (!(i & (1<<u))) ++out;
            }
        }
        if (out <= q) {
            GROUP[i] = true;
            DP[i] = true;
            DPRec[i] = 0;
        }
    }

    F0R(s,1<<n) {
        if (!DP[s]) continue;
        int T = ((1<<n)-1) ^ s;
        for (int t = T; t > 0; t = T & (t-1)) {
            if (GROUP[t]) {
                DP[s | t] = true;
                DPRec[s | t] = s;
            }
        }
    }

    if (DP[(1<<n) - 1]) {
        cout << "home\n";
        vvi ans;
        int s = (1<<n) - 1;
        while (s > 0) {
            int t = DPRec[s] ^ s;
            ans.emplace_back();
            F0R(v,n) {
                if (t & (1<<v)) ans.back().push_back(v);
            }
            s = s ^ t;
        }
        cout << sz(ans) << "\n";
        for (vi xx : ans) {
            cout << sz(xx);
            for (int x : xx) cout << " " << x;
            cout << "\n";
        }
    } else cout << "detention\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 13 ms 468 KB Output is correct
5 Correct 22 ms 468 KB Output is correct
6 Correct 6 ms 444 KB Output is correct
7 Correct 12 ms 464 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 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 1 ms 336 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 13 ms 468 KB Output is correct
5 Correct 22 ms 468 KB Output is correct
6 Correct 6 ms 444 KB Output is correct
7 Correct 12 ms 464 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -