oj.uz

Submission #933735

# Submission time Handle Problem Language Result Execution time Memory
933735 2024-02-26T08:40:46 Z LucaIlie Political Development (BOI17_politicaldevelopment) C++17
4 / 100
 218 ms 4256 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e4;
const int MAX_K = 10;
int perm[MAX_N], pos[MAX_N];
unordered_set<int> adj[MAX_N];

int solve( vector<int> vertices ) {
    int n = vertices.size();
    for ( int i = 0; i < n; i++ )
        pos[vertices[i]] = i;

    int ans = 0;
    for ( int mask = 0; mask < (1 << n); mask++ ) {
        int sz = __builtin_popcount( mask );
        bool ok = true;
        for ( int i = 0; i < n; i++ ) {
            if ( ((mask >> i) & 1) == 0 )
                continue;

            int u = vertices[i];

            int vec = 0;
            for ( int v: adj[u] ) {
                int j = pos[v];
                if ( (mask >> j) & 1 )
                    vec++;
            }

            if ( vec != sz - 1 )
                ok = false;
        }
        if ( ok )
            ans = max( ans, sz );
    }

    return ans;
}

int main() {
    int n, k, minn = n;

    cin >> n >> k;
    for ( int u = 0; u < n; u++ ) {
        int d;
        cin >> d;
        for ( int j = 0; j < d; j++ ) {
            int v;
            cin >> v;
            adj[u].insert( v );
        }
        minn = min( minn, d );
        perm[u] = u;
    }

    int ans = 0;
    for ( int i = 0; i < n - k; i++ ) {
        sort( perm + i, perm + n, []( int u, int v ) {
            return adj[u].size() < adj[v].size();
        } );


        int u = perm[i];
        vector<int> vertices;
        vertices.push_back( u );
        for ( int v: adj[u] ) {
            adj[v].erase( u );
            vertices.push_back( v );
        }
        ans = max( ans, solve( vertices ) );
        adj[u].clear();
    }

    vector<int> vertices;
    for ( int i = n - k; i < n; i++ ) {
        vertices.push_back( perm[i] );
    }

    ans = max( ans, solve( vertices ) );

    cout << ans;

    return 0;
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:43:15: warning: 'n' is used uninitialized in this function [-Wuninitialized]
   43 |     int n, k, minn = n;
      |               ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 137 ms 3932 KB Output is correct
4 Correct 190 ms 4180 KB Output is correct
5 Correct 186 ms 3932 KB Output is correct
6 Correct 133 ms 4188 KB Output is correct
7 Correct 132 ms 4188 KB Output is correct
8 Correct 131 ms 3420 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 124 ms 3164 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 137 ms 3932 KB Output is correct
4 Correct 190 ms 4180 KB Output is correct
5 Correct 186 ms 3932 KB Output is correct
6 Correct 133 ms 4188 KB Output is correct
7 Correct 132 ms 4188 KB Output is correct
8 Correct 131 ms 3420 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 124 ms 3164 KB Output is correct
11 Correct 218 ms 4180 KB Output is correct
12 Correct 199 ms 4256 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 191 ms 4176 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 137 ms 4188 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 163 ms 4188 KB Output is correct
19 Correct 158 ms 3208 KB Output is correct
20 Correct 128 ms 3936 KB Output is correct
21 Correct 128 ms 4184 KB Output is correct
22 Correct 123 ms 3228 KB Output is correct
23 Correct 128 ms 4188 KB Output is correct
24 Correct 127 ms 3420 KB Output is correct
25 Correct 143 ms 4208 KB Output is correct
26 Incorrect 128 ms 3932 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 3160 KB Output is correct
2 Incorrect 1 ms 3160 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 137 ms 3932 KB Output is correct
4 Correct 190 ms 4180 KB Output is correct
5 Correct 186 ms 3932 KB Output is correct
6 Correct 133 ms 4188 KB Output is correct
7 Correct 132 ms 4188 KB Output is correct
8 Correct 131 ms 3420 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 124 ms 3164 KB Output is correct
11 Correct 218 ms 4180 KB Output is correct
12 Correct 199 ms 4256 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 191 ms 4176 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 137 ms 4188 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 163 ms 4188 KB Output is correct
19 Correct 158 ms 3208 KB Output is correct
20 Correct 128 ms 3936 KB Output is correct
21 Correct 128 ms 4184 KB Output is correct
22 Correct 123 ms 3228 KB Output is correct
23 Correct 128 ms 4188 KB Output is correct
24 Correct 127 ms 3420 KB Output is correct
25 Correct 143 ms 4208 KB Output is correct
26 Incorrect 128 ms 3932 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 137 ms 3932 KB Output is correct
4 Correct 190 ms 4180 KB Output is correct
5 Correct 186 ms 3932 KB Output is correct
6 Correct 133 ms 4188 KB Output is correct
7 Correct 132 ms 4188 KB Output is correct
8 Correct 131 ms 3420 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 124 ms 3164 KB Output is correct
11 Correct 218 ms 4180 KB Output is correct
12 Correct 199 ms 4256 KB Output is correct
13 Correct 1 ms 3164 KB Output is correct
14 Correct 191 ms 4176 KB Output is correct
15 Correct 1 ms 3164 KB Output is correct
16 Correct 137 ms 4188 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 163 ms 4188 KB Output is correct
19 Correct 158 ms 3208 KB Output is correct
20 Correct 128 ms 3936 KB Output is correct
21 Correct 128 ms 4184 KB Output is correct
22 Correct 123 ms 3228 KB Output is correct
23 Correct 128 ms 4188 KB Output is correct
24 Correct 127 ms 3420 KB Output is correct
25 Correct 143 ms 4208 KB Output is correct
26 Incorrect 128 ms 3932 KB Output isn't correct
27 Halted 0 ms 0 KB -