oj.uz

Submission #829348

# Submission time Handle Problem Language Result Execution time Memory
829348 2023-08-18T09:41:28 Z Darren0724 Political Development (BOI17_politicaldevelopment) C++17
100 / 100
 1018 ms 28924 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=50005;
vector<int> adj[N],adj1[N];
vector<int> deg(N);
set<pair<int,int>> s;
vector<int> active(N,1);
int calc(int p){
    int sz=adj[p].size();
    //cout<<sz<<endl;
    int g[sz]{};
    for(int i=0;i<sz;i++){
        for(int j=0;j<sz;j++){
            if(i==j||s.find({adj[p][i],adj[p][j]})!=s.end()){
                g[i]|=1<<j;
            }
        }
    }
    int ans=0;
    for(int i=1;i<1<<sz;i++){
        int p=i;
        int cnt=0;
        for(int j=0;j<sz;j++){
            if(i&(1<<j)){
                p&=g[j];
                cnt++;
            }
        }
        if(p==i){
            ans=max(ans,cnt);
        }
    }
    return ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,k;cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>deg[i];
        adj1[i].resize(deg[i]+1);
        adj1[i][0]=i;
        for(int j=1;j<=deg[i];j++){
            cin>>adj1[i][j];
            s.insert({i,adj1[i][j]});
            s.insert({adj1[i][j],i});
        }
    }
    queue<int> q;
    for(int i=0;i<n;i++){
        if(deg[i]<=k){
            q.push(i);
        }
    }
    int ans=0;
    while(q.size()){
        int p=q.front();
        q.pop();
        for(int j:adj1[p]){
            if(active[j]){
                adj[p].push_back(j);
            }
            deg[j]--;
            if(deg[j]==k){
                q.push(j);
            }
        }
        ans=max(ans,calc(p));
        active[p]=0;
    }
    cout<<ans<<endl;



    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 6 ms 3796 KB Output is correct
4 Correct 6 ms 3796 KB Output is correct
5 Correct 6 ms 3924 KB Output is correct
6 Correct 6 ms 3856 KB Output is correct
7 Correct 6 ms 3924 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3076 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 6 ms 3796 KB Output is correct
4 Correct 6 ms 3796 KB Output is correct
5 Correct 6 ms 3924 KB Output is correct
6 Correct 6 ms 3856 KB Output is correct
7 Correct 6 ms 3924 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3076 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 6 ms 3924 KB Output is correct
12 Correct 6 ms 3924 KB Output is correct
13 Correct 1 ms 3076 KB Output is correct
14 Correct 6 ms 3924 KB Output is correct
15 Correct 1 ms 3028 KB Output is correct
16 Correct 7 ms 3924 KB Output is correct
17 Correct 1 ms 3028 KB Output is correct
18 Correct 6 ms 3860 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 4 ms 3668 KB Output is correct
21 Correct 4 ms 3668 KB Output is correct
22 Correct 2 ms 3284 KB Output is correct
23 Correct 8 ms 4052 KB Output is correct
24 Correct 2 ms 3284 KB Output is correct
25 Correct 8 ms 3980 KB Output is correct
26 Correct 8 ms 3924 KB Output is correct
27 Correct 7 ms 3856 KB Output is correct
28 Correct 8 ms 3912 KB Output is correct
29 Correct 7 ms 3852 KB Output is correct
30 Correct 8 ms 3984 KB Output is correct
31 Correct 9 ms 4052 KB Output is correct
32 Correct 9 ms 4052 KB Output is correct
33 Correct 9 ms 3988 KB Output is correct
34 Correct 9 ms 4052 KB Output is correct
35 Correct 5 ms 3540 KB Output is correct
36 Correct 5 ms 3540 KB Output is correct
37 Correct 5 ms 3540 KB Output is correct
38 Correct 4 ms 3380 KB Output is correct
39 Correct 4 ms 3412 KB Output is correct
40 Correct 14 ms 4436 KB Output is correct
41 Correct 5 ms 3488 KB Output is correct
42 Correct 14 ms 4412 KB Output is correct
43 Correct 13 ms 4436 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3284 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 1 ms 3028 KB Output is correct
5 Correct 1 ms 3028 KB Output is correct
6 Correct 1 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 1 ms 3028 KB Output is correct
9 Correct 1 ms 3028 KB Output is correct
10 Correct 1 ms 3028 KB Output is correct
11 Correct 978 ms 28780 KB Output is correct
12 Correct 1 ms 3028 KB Output is correct
13 Correct 1018 ms 28852 KB Output is correct
14 Correct 1 ms 3028 KB Output is correct
15 Correct 1006 ms 28888 KB Output is correct
16 Correct 968 ms 28848 KB Output is correct
17 Correct 993 ms 28924 KB Output is correct
18 Correct 987 ms 28908 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 6 ms 3796 KB Output is correct
4 Correct 6 ms 3796 KB Output is correct
5 Correct 6 ms 3924 KB Output is correct
6 Correct 6 ms 3856 KB Output is correct
7 Correct 6 ms 3924 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3076 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 6 ms 3924 KB Output is correct
12 Correct 6 ms 3924 KB Output is correct
13 Correct 1 ms 3076 KB Output is correct
14 Correct 6 ms 3924 KB Output is correct
15 Correct 1 ms 3028 KB Output is correct
16 Correct 7 ms 3924 KB Output is correct
17 Correct 1 ms 3028 KB Output is correct
18 Correct 6 ms 3860 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 4 ms 3668 KB Output is correct
21 Correct 4 ms 3668 KB Output is correct
22 Correct 2 ms 3284 KB Output is correct
23 Correct 8 ms 4052 KB Output is correct
24 Correct 2 ms 3284 KB Output is correct
25 Correct 8 ms 3980 KB Output is correct
26 Correct 8 ms 3924 KB Output is correct
27 Correct 7 ms 3856 KB Output is correct
28 Correct 8 ms 3912 KB Output is correct
29 Correct 7 ms 3852 KB Output is correct
30 Correct 8 ms 3984 KB Output is correct
31 Correct 9 ms 4052 KB Output is correct
32 Correct 9 ms 4052 KB Output is correct
33 Correct 9 ms 3988 KB Output is correct
34 Correct 9 ms 4052 KB Output is correct
35 Correct 5 ms 3540 KB Output is correct
36 Correct 5 ms 3540 KB Output is correct
37 Correct 5 ms 3540 KB Output is correct
38 Correct 4 ms 3380 KB Output is correct
39 Correct 4 ms 3412 KB Output is correct
40 Correct 14 ms 4436 KB Output is correct
41 Correct 5 ms 3488 KB Output is correct
42 Correct 14 ms 4412 KB Output is correct
43 Correct 13 ms 4436 KB Output is correct
44 Correct 41 ms 5644 KB Output is correct
45 Correct 1 ms 3028 KB Output is correct
46 Correct 14 ms 4436 KB Output is correct
47 Correct 32 ms 5572 KB Output is correct
48 Correct 13 ms 4436 KB Output is correct
49 Correct 34 ms 5588 KB Output is correct
50 Correct 36 ms 5528 KB Output is correct
51 Correct 179 ms 8160 KB Output is correct
52 Correct 5 ms 3924 KB Output is correct
53 Correct 261 ms 8432 KB Output is correct
54 Correct 345 ms 8496 KB Output is correct
55 Correct 6 ms 3924 KB Output is correct
56 Correct 5 ms 3924 KB Output is correct
57 Correct 2 ms 3412 KB Output is correct
58 Correct 254 ms 8444 KB Output is correct
59 Correct 13 ms 4436 KB Output is correct
60 Correct 6 ms 3924 KB Output is correct
61 Correct 13 ms 4436 KB Output is correct
62 Correct 13 ms 4436 KB Output is correct
63 Correct 41 ms 5476 KB Output is correct
64 Correct 28 ms 5224 KB Output is correct
65 Correct 12 ms 4256 KB Output is correct
66 Correct 13 ms 4388 KB Output is correct
67 Correct 86 ms 6072 KB Output is correct
68 Correct 28 ms 5320 KB Output is correct
69 Correct 12 ms 4308 KB Output is correct
70 Correct 33 ms 5320 KB Output is correct
71 Correct 73 ms 5964 KB Output is correct
72 Correct 67 ms 5852 KB Output is correct
73 Correct 7 ms 3924 KB Output is correct
74 Correct 34 ms 5380 KB Output is correct
75 Correct 77 ms 5940 KB Output is correct
76 Correct 19 ms 4820 KB Output is correct
77 Correct 124 ms 6544 KB Output is correct
78 Correct 7 ms 3848 KB Output is correct
79 Correct 61 ms 4740 KB Output is correct
80 Correct 19 ms 4820 KB Output is correct
81 Correct 133 ms 6536 KB Output is correct
82 Correct 4 ms 3412 KB Output is correct
83 Correct 61 ms 4804 KB Output is correct
84 Correct 69 ms 5752 KB Output is correct
85 Correct 4 ms 3412 KB Output is correct
86 Correct 69 ms 5812 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3028 KB Output is correct
2 Correct 1 ms 3028 KB Output is correct
3 Correct 6 ms 3796 KB Output is correct
4 Correct 6 ms 3796 KB Output is correct
5 Correct 6 ms 3924 KB Output is correct
6 Correct 6 ms 3856 KB Output is correct
7 Correct 6 ms 3924 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3076 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 6 ms 3924 KB Output is correct
12 Correct 6 ms 3924 KB Output is correct
13 Correct 1 ms 3076 KB Output is correct
14 Correct 6 ms 3924 KB Output is correct
15 Correct 1 ms 3028 KB Output is correct
16 Correct 7 ms 3924 KB Output is correct
17 Correct 1 ms 3028 KB Output is correct
18 Correct 6 ms 3860 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 4 ms 3668 KB Output is correct
21 Correct 4 ms 3668 KB Output is correct
22 Correct 2 ms 3284 KB Output is correct
23 Correct 8 ms 4052 KB Output is correct
24 Correct 2 ms 3284 KB Output is correct
25 Correct 8 ms 3980 KB Output is correct
26 Correct 8 ms 3924 KB Output is correct
27 Correct 7 ms 3856 KB Output is correct
28 Correct 8 ms 3912 KB Output is correct
29 Correct 7 ms 3852 KB Output is correct
30 Correct 8 ms 3984 KB Output is correct
31 Correct 9 ms 4052 KB Output is correct
32 Correct 9 ms 4052 KB Output is correct
33 Correct 9 ms 3988 KB Output is correct
34 Correct 9 ms 4052 KB Output is correct
35 Correct 5 ms 3540 KB Output is correct
36 Correct 5 ms 3540 KB Output is correct
37 Correct 5 ms 3540 KB Output is correct
38 Correct 4 ms 3380 KB Output is correct
39 Correct 4 ms 3412 KB Output is correct
40 Correct 14 ms 4436 KB Output is correct
41 Correct 5 ms 3488 KB Output is correct
42 Correct 14 ms 4412 KB Output is correct
43 Correct 13 ms 4436 KB Output is correct
44 Correct 2 ms 3028 KB Output is correct
45 Correct 352 ms 22680 KB Output is correct
46 Correct 123 ms 14196 KB Output is correct
47 Correct 341 ms 22888 KB Output is correct
48 Correct 418 ms 22656 KB Output is correct
49 Correct 59 ms 11724 KB Output is correct
50 Correct 314 ms 28820 KB Output is correct
51 Correct 353 ms 22840 KB Output is correct
52 Correct 82 ms 11728 KB Output is correct
53 Correct 60 ms 11780 KB Output is correct
54 Correct 9 ms 6284 KB Output is correct
55 Correct 328 ms 28856 KB Output is correct
56 Correct 43 ms 8944 KB Output is correct
57 Correct 63 ms 11724 KB Output is correct
58 Correct 113 ms 14160 KB Output is correct
59 Correct 34 ms 8860 KB Output is correct
60 Correct 34 ms 8908 KB Output is correct
61 Correct 113 ms 14104 KB Output is correct
62 Correct 71 ms 11500 KB Output is correct
63 Correct 158 ms 15632 KB Output is correct
64 Correct 34 ms 8908 KB Output is correct
65 Correct 224 ms 18548 KB Output is correct
66 Correct 69 ms 11492 KB Output is correct
67 Correct 164 ms 15608 KB Output is correct
68 Correct 209 ms 17736 KB Output is correct
69 Correct 211 ms 18508 KB Output is correct
70 Correct 69 ms 11564 KB Output is correct
71 Correct 235 ms 17828 KB Output is correct
72 Correct 133 ms 15240 KB Output is correct
73 Correct 250 ms 20212 KB Output is correct
74 Correct 70 ms 11444 KB Output is correct
75 Correct 80 ms 9996 KB Output is correct
76 Correct 131 ms 15232 KB Output is correct
77 Correct 273 ms 20280 KB Output is correct
78 Correct 105 ms 11552 KB Output is correct
79 Correct 81 ms 9924 KB Output is correct
80 Correct 32 ms 6476 KB Output is correct
81 Correct 102 ms 11568 KB Output is correct
82 Correct 169 ms 16928 KB Output is correct
83 Correct 32 ms 6476 KB Output is correct
84 Correct 239 ms 16940 KB Output is correct