oj.uz

Submission #933741

# Submission time Handle Problem Language Result Execution time Memory
933741 2024-02-26T08:51:57 Z LucaIlie Political Development (BOI17_politicaldevelopment) C++17
4 / 100
 3000 ms 25128 KB 
#include <bits/stdc++.h>

using namespace std;

struct pv {
    int u, a;

    bool operator < ( const pv &x ) const {
        if ( a == x.a )
            return u < x.u;
        return a < x.a;
    }
};

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

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 ( j != -1 && ((mask >> j) & 1) )
                    vec++;
            }

            if ( vec != sz - 1 )
                ok = false;
        }
        if ( ok )
            ans = max( ans, sz );
    }
    for ( int i = 0; i < n; i++ )
        pos[vertices[i]] = -1;

    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 );
        vertMinSize.insert( { u, d } );
    }
    for ( int i = 0; i < n; i++ )
        pos[i] = -1;

    int ans = 0;
    for ( int i = 0; i < n; i++ ) {
        int u = vertMinSize.begin()->u;

        vector<int> vertices;
        vertices.push_back( u );
        for ( int v: adj[u] )
            vertices.push_back( v );
        ans = max( ans, solve( vertices ) );

        vertMinSize.erase( { u, (int)adj[u].size() } );
        adj[u].clear();
        for ( int v: adj[u] ) {
            vertMinSize.erase( { v, (int)adj[v].size() } );
            adj[v].erase( v );
            vertMinSize.insert( { v, (int)adj[v].size() } );
        }
    }

    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:56:15: warning: 'n' is used uninitialized in this function [-Wuninitialized]
   56 |     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 11 ms 4184 KB Output is correct
4 Correct 119 ms 4324 KB Output is correct
5 Correct 120 ms 4312 KB Output is correct
6 Correct 13 ms 4188 KB Output is correct
7 Correct 12 ms 4272 KB Output is correct
8 Correct 3 ms 3416 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 3 ms 3432 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 11 ms 4184 KB Output is correct
4 Correct 119 ms 4324 KB Output is correct
5 Correct 120 ms 4312 KB Output is correct
6 Correct 13 ms 4188 KB Output is correct
7 Correct 12 ms 4272 KB Output is correct
8 Correct 3 ms 3416 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 3 ms 3432 KB Output is correct
11 Correct 125 ms 4312 KB Output is correct
12 Correct 120 ms 4312 KB Output is correct
13 Correct 1 ms 3160 KB Output is correct
14 Correct 119 ms 4188 KB Output is correct
15 Correct 1 ms 3160 KB Output is correct
16 Correct 13 ms 4188 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 13 ms 4188 KB Output is correct
19 Correct 3 ms 3420 KB Output is correct
20 Correct 5 ms 3932 KB Output is correct
21 Correct 5 ms 3932 KB Output is correct
22 Correct 3 ms 3232 KB Output is correct
23 Correct 10 ms 4188 KB Output is correct
24 Correct 3 ms 3420 KB Output is correct
25 Correct 10 ms 4188 KB Output is correct
26 Correct 9 ms 4232 KB Output is correct
27 Correct 7 ms 4188 KB Output is correct
28 Correct 9 ms 4188 KB Output is correct
29 Correct 7 ms 4104 KB Output is correct
30 Correct 90 ms 4428 KB Output is correct
31 Correct 9 ms 4188 KB Output is correct
32 Correct 89 ms 4424 KB Output is correct
33 Correct 9 ms 4184 KB Output is correct
34 Correct 9 ms 4188 KB Output is correct
35 Correct 5 ms 3676 KB Output is correct
36 Correct 5 ms 3676 KB Output is correct
37 Correct 5 ms 3676 KB Output is correct
38 Execution timed out 3043 ms 3416 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 1 ms 3412 KB Output is correct
6 Correct 1 ms 3172 KB Output is correct
7 Correct 1 ms 3164 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 1 ms 3164 KB Output is correct
11 Execution timed out 3082 ms 25128 KB Time limit exceeded
12 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 11 ms 4184 KB Output is correct
4 Correct 119 ms 4324 KB Output is correct
5 Correct 120 ms 4312 KB Output is correct
6 Correct 13 ms 4188 KB Output is correct
7 Correct 12 ms 4272 KB Output is correct
8 Correct 3 ms 3416 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 3 ms 3432 KB Output is correct
11 Correct 125 ms 4312 KB Output is correct
12 Correct 120 ms 4312 KB Output is correct
13 Correct 1 ms 3160 KB Output is correct
14 Correct 119 ms 4188 KB Output is correct
15 Correct 1 ms 3160 KB Output is correct
16 Correct 13 ms 4188 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 13 ms 4188 KB Output is correct
19 Correct 3 ms 3420 KB Output is correct
20 Correct 5 ms 3932 KB Output is correct
21 Correct 5 ms 3932 KB Output is correct
22 Correct 3 ms 3232 KB Output is correct
23 Correct 10 ms 4188 KB Output is correct
24 Correct 3 ms 3420 KB Output is correct
25 Correct 10 ms 4188 KB Output is correct
26 Correct 9 ms 4232 KB Output is correct
27 Correct 7 ms 4188 KB Output is correct
28 Correct 9 ms 4188 KB Output is correct
29 Correct 7 ms 4104 KB Output is correct
30 Correct 90 ms 4428 KB Output is correct
31 Correct 9 ms 4188 KB Output is correct
32 Correct 89 ms 4424 KB Output is correct
33 Correct 9 ms 4184 KB Output is correct
34 Correct 9 ms 4188 KB Output is correct
35 Correct 5 ms 3676 KB Output is correct
36 Correct 5 ms 3676 KB Output is correct
37 Correct 5 ms 3676 KB Output is correct
38 Execution timed out 3043 ms 3416 KB Time limit exceeded
39 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 11 ms 4184 KB Output is correct
4 Correct 119 ms 4324 KB Output is correct
5 Correct 120 ms 4312 KB Output is correct
6 Correct 13 ms 4188 KB Output is correct
7 Correct 12 ms 4272 KB Output is correct
8 Correct 3 ms 3416 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 3 ms 3432 KB Output is correct
11 Correct 125 ms 4312 KB Output is correct
12 Correct 120 ms 4312 KB Output is correct
13 Correct 1 ms 3160 KB Output is correct
14 Correct 119 ms 4188 KB Output is correct
15 Correct 1 ms 3160 KB Output is correct
16 Correct 13 ms 4188 KB Output is correct
17 Correct 1 ms 3164 KB Output is correct
18 Correct 13 ms 4188 KB Output is correct
19 Correct 3 ms 3420 KB Output is correct
20 Correct 5 ms 3932 KB Output is correct
21 Correct 5 ms 3932 KB Output is correct
22 Correct 3 ms 3232 KB Output is correct
23 Correct 10 ms 4188 KB Output is correct
24 Correct 3 ms 3420 KB Output is correct
25 Correct 10 ms 4188 KB Output is correct
26 Correct 9 ms 4232 KB Output is correct
27 Correct 7 ms 4188 KB Output is correct
28 Correct 9 ms 4188 KB Output is correct
29 Correct 7 ms 4104 KB Output is correct
30 Correct 90 ms 4428 KB Output is correct
31 Correct 9 ms 4188 KB Output is correct
32 Correct 89 ms 4424 KB Output is correct
33 Correct 9 ms 4184 KB Output is correct
34 Correct 9 ms 4188 KB Output is correct
35 Correct 5 ms 3676 KB Output is correct
36 Correct 5 ms 3676 KB Output is correct
37 Correct 5 ms 3676 KB Output is correct
38 Execution timed out 3043 ms 3416 KB Time limit exceeded
39 Halted 0 ms 0 KB -