oj.uz

Submission #557876

# Submission time Handle Problem Language Result Execution time Memory
557876 2022-05-06T08:36:05 Z fatemetmhr Friends (BOI17_friends) C++17
20 / 100
 1000 ms 360 KB 
// ~Be name khoda~ //
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define pb     push_back
#define all(x) x.begin(), x.end()
#define fi     first
#define se     second
 
const int maxn5 = 200 + 10;

int n, p, q;
bool dp[1 << 20];
int par[1 << 20], av[maxn5];
vector <int> out, adj[maxn5];
bool ed[maxn5][maxn5];
 

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
    cin >> n >> p >> q;

    for(int i = 0; i < n; i++){
        int l; cin >> l;
        while(l--){
            int a; cin >> a;
            adj[i].pb(a);
            ed[i][a] = true;
        }
    }
    for(int i = 0; i < n; i++) for(auto u : adj[i])
        if(!ed[u][i])
            return cout << "detention" << endl, 0;
    dp[0] = true;
    for(int mask = 1; mask < (1 << n); mask++){
        int pt = 0;
        for(int i = 0; i < n; i++) if((mask >> i)&1)
            av[pt++] = i;
        for(int s = 0; s < (1 << (pt - 1)); s++) if(__builtin_popcount(s) < p){
            int sub = s + (1 << (pt - 1));
            int sum = 0;
            for(int i = 0; i < pt; i++) if((sub >> i)&1){
                for(auto u : adj[av[i]]) if(1 ^ ((sub >> u)&1))
                    sum++; 
            }
            if(sum <= q && dp[mask ^ sub]){
                dp[mask] = true;
                par[mask] = sub;
            }
        }
    }
    if(!dp[(1 << n) - 1])
        return cout << "detention" << endl, 0;
    cout << "home" << endl;
    int mask = (1 << n) - 1;
    while(mask){
        out.pb(par[mask]);
        mask ^= par[mask];
    }
    cout << out.size() << endl;
    for(auto mask : out){
        cout << __builtin_popcount(mask) << ' ';
        for(int i = 0; i < n; i++) if((mask >> i)&1)
            cout << i << ' ';
        cout << endl;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 36 ms 340 KB Output is correct
5 Correct 146 ms 360 KB Output is correct
6 Correct 316 ms 344 KB Output is correct
7 Correct 135 ms 340 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 212 KB Output is correct
2 Execution timed out 1089 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 1089 ms 348 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 36 ms 340 KB Output is correct
5 Correct 146 ms 360 KB Output is correct
6 Correct 316 ms 344 KB Output is correct
7 Correct 135 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Execution timed out 1089 ms 348 KB Time limit exceeded
11 Halted 0 ms 0 KB -