oj.uz

Submission #785756

# Submission time Handle Problem Language Result Execution time Memory
785756 2023-07-17T14:37:49 Z SlavicG Political Development (BOI17_politicaldevelopment) C++17
27 / 100
 467 ms 28704 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 5e4 + 10;
unordered_set<int> st[N];
vector<int> adj[N];
int ans = 1;

void solve() {
    int n, k; cin >> n >> k;
    for(int i = 0; i < n; ++i) {
        int x; cin >> x; 
        if(x >= 1) {
            adj[i].resize(x);
            for(int j = 0; j < x; ++j) {
                cin >> adj[i][j];
                st[i].insert(adj[i][j]);
                st[adj[i][j]].insert(i);
            }
        } 
    }
    
    for(int i = 0; i < n; ++i) {
        if(sz(adj[i]) >= k) {
            ans = max(ans, 2);
            continue;
        }
        vector<int> dp(1 << (sz(adj[i])), 0);
        dp[0] = 1;
        for(int mask = 0; mask < (1 << (sz(adj[i]))); ++mask) {
            if(!dp[mask]) continue;
            int cnt = 1;
            for(int f = 0; f < sz(adj[i]); ++f) {
                if(mask >> f & 1) ++cnt;
            }
            ans = max(ans, cnt);
            for(int j = 0; j < sz(adj[i]); ++j) {
                if(mask >> j & 1) continue;
                bool check = true;
                for(int f = 0; f < sz(adj[i]); ++f) {
                    if(mask >> f & 1) {
                        if(st[adj[i][j]].find(adj[i][f]) == st[adj[i][j]].end()) check = false;
                    }
                }
                if(check) dp[mask | (1 << j)] = 1;
            }
        }
    }
    cout << ans << "\n";
}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4236 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 6 ms 5320 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 2 ms 4228 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4236 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 6 ms 5320 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 2 ms 4228 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 4 ms 5344 KB Output is correct
13 Correct 2 ms 4236 KB Output is correct
14 Correct 5 ms 5260 KB Output is correct
15 Correct 2 ms 4180 KB Output is correct
16 Correct 7 ms 5324 KB Output is correct
17 Correct 2 ms 4308 KB Output is correct
18 Correct 7 ms 5400 KB Output is correct
19 Correct 3 ms 4244 KB Output is correct
20 Correct 4 ms 5120 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 2 ms 4180 KB Output is correct
23 Incorrect 5 ms 5332 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4240 KB Output is correct
2 Correct 2 ms 4240 KB Output is correct
3 Correct 2 ms 4180 KB Output is correct
4 Correct 2 ms 4180 KB Output is correct
5 Correct 2 ms 4180 KB Output is correct
6 Correct 3 ms 4180 KB Output is correct
7 Correct 2 ms 4180 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 2 ms 4180 KB Output is correct
10 Correct 3 ms 4180 KB Output is correct
11 Correct 396 ms 28704 KB Output is correct
12 Correct 2 ms 4180 KB Output is correct
13 Correct 434 ms 27284 KB Output is correct
14 Correct 2 ms 4180 KB Output is correct
15 Correct 439 ms 27292 KB Output is correct
16 Correct 433 ms 27292 KB Output is correct
17 Correct 410 ms 27196 KB Output is correct
18 Correct 467 ms 27292 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4236 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 6 ms 5320 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 2 ms 4228 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 4 ms 5344 KB Output is correct
13 Correct 2 ms 4236 KB Output is correct
14 Correct 5 ms 5260 KB Output is correct
15 Correct 2 ms 4180 KB Output is correct
16 Correct 7 ms 5324 KB Output is correct
17 Correct 2 ms 4308 KB Output is correct
18 Correct 7 ms 5400 KB Output is correct
19 Correct 3 ms 4244 KB Output is correct
20 Correct 4 ms 5120 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 2 ms 4180 KB Output is correct
23 Incorrect 5 ms 5332 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4236 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct
3 Correct 5 ms 5204 KB Output is correct
4 Correct 6 ms 5320 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 5 ms 5332 KB Output is correct
7 Correct 5 ms 5332 KB Output is correct
8 Correct 2 ms 4180 KB Output is correct
9 Correct 2 ms 4228 KB Output is correct
10 Correct 2 ms 4180 KB Output is correct
11 Correct 5 ms 5332 KB Output is correct
12 Correct 4 ms 5344 KB Output is correct
13 Correct 2 ms 4236 KB Output is correct
14 Correct 5 ms 5260 KB Output is correct
15 Correct 2 ms 4180 KB Output is correct
16 Correct 7 ms 5324 KB Output is correct
17 Correct 2 ms 4308 KB Output is correct
18 Correct 7 ms 5400 KB Output is correct
19 Correct 3 ms 4244 KB Output is correct
20 Correct 4 ms 5120 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 2 ms 4180 KB Output is correct
23 Incorrect 5 ms 5332 KB Output isn't correct
24 Halted 0 ms 0 KB -