oj.uz

Submission #372017

# Submission time Handle Problem Language Result Execution time Memory
372017 2021-02-27T07:51:10 Z gustason April Fools (LMIO17_faktai) C++11
100 / 100
 505 ms 492 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, f;
vector<vector<int>> a;
bool check(vector<bool> fact) {
    for(int i = 0; i < n; i++) {
        int cnt = 0;
        for(int j = 0; j < (int) a[i].size(); j++) {
            if (fact[a[i][j]] == false) {
                cnt++;
            }
        }
        if (cnt != 1) return false;
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> f;
    a.resize(n);
    for(int i = 0; i < n; i++) {
        int k;
        cin >> k;
        a[i].resize(k);
        for(int j = 0; j < k; j++) {
            cin >> a[i][j];
            a[i][j]--;
        }
    }

    int mn = f+1, mx = 0;
    for(int mask = 0; mask < (1 << f); mask++) {
        vector<bool> facts(f, false);
        int cnt = f;
        for(int i = 0; i < f; i++) {
            if (mask & (1 << i)) {
                facts[i] = true;
                cnt--;
            }
        }
//        for(auto i : facts) {
//            cout << i << " ";
//        } cout << "\n";
        int fun = check(facts);
//        cout << fun << "\n";
        if (fun == true) {
            mn = min(mn, cnt);
            mx = max(mx, cnt);
        }
    }
    cout << mn << " " << mx << "\n";
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 226 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 237 ms 364 KB Output is correct
9 Correct 234 ms 364 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 226 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 237 ms 364 KB Output is correct
5 Correct 234 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 204 ms 392 KB Output is correct
14 Correct 230 ms 364 KB Output is correct
15 Correct 261 ms 364 KB Output is correct
16 Correct 505 ms 492 KB Output is correct
17 Correct 224 ms 412 KB Output is correct
18 Correct 232 ms 416 KB Output is correct
19 Correct 305 ms 364 KB Output is correct