oj.uz

Submission #557538

# Submission time Handle Problem Language Result Execution time Memory
557538 2022-05-05T12:45:45 Z fatemetmhr Political Development (BOI17_politicaldevelopment) C++17
23 / 100
 846 ms 42780 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 = 2e5 + 10;

set <int> adjset[maxn5];
vector <int> adj[maxn5], ver;
priority_queue <pair<int, int>> av;
bool ed[20][20], mark[maxn5], dp[1 << 20];
int cnt[maxn5];

inline int max_indep(){
    int n = ver.size();
    assert(n <= 10);
    memset(ed, false, sizeof ed);
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)
        if(adjset[ver[i]].find(ver[j]) != adjset[ver[i]].end())
            ed[i][j] = true;
    dp[0] = true;
    int ans = 0;
    for(int mask = 1; mask < (1 << n); mask++){
        int v = -1;
        dp[mask] = true;
        for(int i = 0; i < n; i++) if((mask >> i)&1){
            if(v == -1){
                v = i;
                dp[mask] = dp[mask ^ (1 << i)];
            }
            else
                dp[mask] &= ed[v][i];
        }
        if(dp[mask])
            ans = max(ans, __builtin_popcount(mask));
    }
    return ans;
}

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

    int n, k; cin >> n >> k;
    for(int i = 0; i < n; i++){
        int l; cin >> l;
        cnt[i] = l;
        while(l--){
            int a; cin >> a;
            adj[i].pb(a);
            adjset[i].insert(a);
            assert(a != i);
        }
        av.push({-cnt[i], i});
    }
    for(int i = 0; i < n; i++) for(auto u : adj[i])
        assert(adjset[u].find(i) != adjset[u].end());
    int ans = 0;
    for(int i = 0; i < n; i++){
        ver.clear();
        for(auto u : adj[i])
            ver.pb(u);
        ans = max(ans, max_indep() + 1);
    }
    /*
    for(int i = 0; i < n; i++){
        while(mark[av.top().se])
            av.pop();
        int v = av.top().se;
        av.pop();
        mark[v] = true;
        ver.clear();
        for(auto u : adj[v]) if(!mark[u]){
            cnt[u]--;
            av.push({-cnt[u], u});
            ver.pb(u);
        }
        ans = max(ans, max_indep() + 1);
    }
    */
    cout << ans << endl;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Runtime error 30 ms 30480 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Runtime error 30 ms 30480 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14548 KB Output is correct
2 Correct 8 ms 14472 KB Output is correct
3 Correct 8 ms 14392 KB Output is correct
4 Correct 8 ms 14420 KB Output is correct
5 Correct 8 ms 14420 KB Output is correct
6 Correct 9 ms 14420 KB Output is correct
7 Correct 8 ms 14420 KB Output is correct
8 Correct 9 ms 14420 KB Output is correct
9 Correct 8 ms 14424 KB Output is correct
10 Correct 8 ms 14332 KB Output is correct
11 Correct 777 ms 42696 KB Output is correct
12 Correct 9 ms 14420 KB Output is correct
13 Correct 804 ms 42704 KB Output is correct
14 Correct 8 ms 14420 KB Output is correct
15 Correct 773 ms 42780 KB Output is correct
16 Correct 769 ms 42700 KB Output is correct
17 Correct 834 ms 42704 KB Output is correct
18 Correct 846 ms 42700 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Runtime error 30 ms 30480 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 7 ms 14292 KB Output is correct
3 Runtime error 30 ms 30480 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -