oj.uz

Submission #934914

# Submission time Handle Problem Language Result Execution time Memory
934914 2024-02-28T07:29:47 Z irmuun Political Development (BOI17_politicaldevelopment) C++17
39 / 100
 621 ms 340052 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

ll n,k,d[50000];
vector<ll>adj[50000];
vector<vector<bool>>dis(50000,vector<bool>(50000,0));
bool check(vector<ll>v){
    for(ll i=0;i<v.size();i++){
        for(ll j=i+1;j<v.size();j++){
            if(dis[v[i]][v[j]]==false){
                return false;
            }
        }
    }
    return true;
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    set<ll>adj[n];
    set<pair<ll,ll>>ord;
    for(ll i=0;i<n;i++){
        cin>>d[i];
        ord.insert({d[i],i});
        for(ll j=0;j<d[i];j++){
            ll u;
            cin>>u;
            adj[i].insert(u);
            dis[i][u]=true;
        }
    }
    ll ans=1;
    while(!ord.empty()){
        auto [s,i]=*ord.begin();
        ord.erase(ord.begin());
        ll sz=adj[i].size();
        ll p=(1ll<<sz);
        vector<ll>v;
        for(ll j=0;j<p;j++){
            ll r=0;
            for(auto x:adj[i]){
                if(j&(1ll<<r)){
                    v.pb(x);
                }
            }
            if(check(v)){
                ans=max(ans,(ll)v.size()+1);
            }
            v.clear();
        }
        for(auto x:adj[i]){
            ll y=adj[x].size();
            adj[x].erase(i);
            ord.erase({y,x});
            ord.insert({y-1,x});
        }
    }
    cout<<ans;
}

Compilation message

politicaldevelopment.cpp: In function 'bool check(std::vector<long long int>)':
politicaldevelopment.cpp:16:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(ll i=0;i<v.size();i++){
      |                ~^~~~~~~~~
politicaldevelopment.cpp:17:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(ll j=i+1;j<v.size();j++){
      |                      ~^~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 310376 KB Output is correct
2 Correct 152 ms 310416 KB Output is correct
3 Correct 154 ms 311468 KB Output is correct
4 Correct 146 ms 311380 KB Output is correct
5 Correct 144 ms 311488 KB Output is correct
6 Correct 152 ms 311464 KB Output is correct
7 Correct 149 ms 311480 KB Output is correct
8 Correct 149 ms 311012 KB Output is correct
9 Correct 143 ms 310384 KB Output is correct
10 Correct 142 ms 310908 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 310376 KB Output is correct
2 Correct 152 ms 310416 KB Output is correct
3 Correct 154 ms 311468 KB Output is correct
4 Correct 146 ms 311380 KB Output is correct
5 Correct 144 ms 311488 KB Output is correct
6 Correct 152 ms 311464 KB Output is correct
7 Correct 149 ms 311480 KB Output is correct
8 Correct 149 ms 311012 KB Output is correct
9 Correct 143 ms 310384 KB Output is correct
10 Correct 142 ms 310908 KB Output is correct
11 Correct 148 ms 311380 KB Output is correct
12 Correct 149 ms 311520 KB Output is correct
13 Correct 159 ms 310388 KB Output is correct
14 Correct 145 ms 311512 KB Output is correct
15 Correct 147 ms 310360 KB Output is correct
16 Correct 153 ms 311484 KB Output is correct
17 Correct 164 ms 310356 KB Output is correct
18 Correct 151 ms 311380 KB Output is correct
19 Correct 154 ms 310936 KB Output is correct
20 Correct 148 ms 311040 KB Output is correct
21 Correct 146 ms 311112 KB Output is correct
22 Correct 148 ms 310860 KB Output is correct
23 Correct 151 ms 311492 KB Output is correct
24 Correct 145 ms 310840 KB Output is correct
25 Correct 159 ms 311636 KB Output is correct
26 Correct 151 ms 311572 KB Output is correct
27 Correct 162 ms 311376 KB Output is correct
28 Correct 162 ms 311516 KB Output is correct
29 Correct 151 ms 311408 KB Output is correct
30 Correct 156 ms 311572 KB Output is correct
31 Correct 151 ms 311472 KB Output is correct
32 Correct 156 ms 311648 KB Output is correct
33 Correct 154 ms 311660 KB Output is correct
34 Correct 161 ms 311636 KB Output is correct
35 Correct 152 ms 311068 KB Output is correct
36 Correct 149 ms 310868 KB Output is correct
37 Correct 159 ms 311220 KB Output is correct
38 Correct 148 ms 310820 KB Output is correct
39 Correct 144 ms 310592 KB Output is correct
40 Correct 150 ms 312008 KB Output is correct
41 Correct 144 ms 310608 KB Output is correct
42 Correct 155 ms 311940 KB Output is correct
43 Correct 159 ms 311936 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 310952 KB Output is correct
2 Correct 159 ms 310416 KB Output is correct
3 Correct 150 ms 310272 KB Output is correct
4 Correct 143 ms 310220 KB Output is correct
5 Correct 143 ms 310340 KB Output is correct
6 Correct 153 ms 310364 KB Output is correct
7 Correct 144 ms 310280 KB Output is correct
8 Correct 142 ms 310368 KB Output is correct
9 Correct 144 ms 310352 KB Output is correct
10 Correct 145 ms 310360 KB Output is correct
11 Correct 567 ms 339932 KB Output is correct
12 Correct 148 ms 310248 KB Output is correct
13 Correct 613 ms 340052 KB Output is correct
14 Correct 143 ms 310344 KB Output is correct
15 Correct 621 ms 339920 KB Output is correct
16 Correct 620 ms 339924 KB Output is correct
17 Correct 613 ms 340048 KB Output is correct
18 Correct 619 ms 339916 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 310376 KB Output is correct
2 Correct 152 ms 310416 KB Output is correct
3 Correct 154 ms 311468 KB Output is correct
4 Correct 146 ms 311380 KB Output is correct
5 Correct 144 ms 311488 KB Output is correct
6 Correct 152 ms 311464 KB Output is correct
7 Correct 149 ms 311480 KB Output is correct
8 Correct 149 ms 311012 KB Output is correct
9 Correct 143 ms 310384 KB Output is correct
10 Correct 142 ms 310908 KB Output is correct
11 Correct 148 ms 311380 KB Output is correct
12 Correct 149 ms 311520 KB Output is correct
13 Correct 159 ms 310388 KB Output is correct
14 Correct 145 ms 311512 KB Output is correct
15 Correct 147 ms 310360 KB Output is correct
16 Correct 153 ms 311484 KB Output is correct
17 Correct 164 ms 310356 KB Output is correct
18 Correct 151 ms 311380 KB Output is correct
19 Correct 154 ms 310936 KB Output is correct
20 Correct 148 ms 311040 KB Output is correct
21 Correct 146 ms 311112 KB Output is correct
22 Correct 148 ms 310860 KB Output is correct
23 Correct 151 ms 311492 KB Output is correct
24 Correct 145 ms 310840 KB Output is correct
25 Correct 159 ms 311636 KB Output is correct
26 Correct 151 ms 311572 KB Output is correct
27 Correct 162 ms 311376 KB Output is correct
28 Correct 162 ms 311516 KB Output is correct
29 Correct 151 ms 311408 KB Output is correct
30 Correct 156 ms 311572 KB Output is correct
31 Correct 151 ms 311472 KB Output is correct
32 Correct 156 ms 311648 KB Output is correct
33 Correct 154 ms 311660 KB Output is correct
34 Correct 161 ms 311636 KB Output is correct
35 Correct 152 ms 311068 KB Output is correct
36 Correct 149 ms 310868 KB Output is correct
37 Correct 159 ms 311220 KB Output is correct
38 Correct 148 ms 310820 KB Output is correct
39 Correct 144 ms 310592 KB Output is correct
40 Correct 150 ms 312008 KB Output is correct
41 Correct 144 ms 310608 KB Output is correct
42 Correct 155 ms 311940 KB Output is correct
43 Correct 159 ms 311936 KB Output is correct
44 Correct 174 ms 313168 KB Output is correct
45 Correct 143 ms 310296 KB Output is correct
46 Correct 152 ms 311888 KB Output is correct
47 Correct 177 ms 312860 KB Output is correct
48 Correct 149 ms 311992 KB Output is correct
49 Correct 165 ms 313064 KB Output is correct
50 Correct 162 ms 312808 KB Output is correct
51 Correct 235 ms 315108 KB Output is correct
52 Correct 152 ms 311372 KB Output is correct
53 Correct 295 ms 315572 KB Output is correct
54 Correct 304 ms 315444 KB Output is correct
55 Correct 156 ms 311532 KB Output is correct
56 Correct 160 ms 311500 KB Output is correct
57 Correct 150 ms 310968 KB Output is correct
58 Correct 288 ms 315476 KB Output is correct
59 Correct 157 ms 312056 KB Output is correct
60 Correct 146 ms 311380 KB Output is correct
61 Correct 156 ms 311892 KB Output is correct
62 Correct 154 ms 311892 KB Output is correct
63 Correct 173 ms 313088 KB Output is correct
64 Correct 164 ms 312676 KB Output is correct
65 Correct 162 ms 311720 KB Output is correct
66 Correct 155 ms 311888 KB Output is correct
67 Correct 173 ms 313428 KB Output is correct
68 Correct 163 ms 312836 KB Output is correct
69 Correct 158 ms 311824 KB Output is correct
70 Correct 159 ms 312660 KB Output is correct
71 Correct 174 ms 313328 KB Output is correct
72 Correct 176 ms 313468 KB Output is correct
73 Correct 149 ms 311308 KB Output is correct
74 Correct 161 ms 312688 KB Output is correct
75 Correct 178 ms 313428 KB Output is correct
76 Correct 155 ms 312228 KB Output is correct
77 Correct 187 ms 314140 KB Output is correct
78 Correct 147 ms 311384 KB Output is correct
79 Correct 162 ms 312120 KB Output is correct
80 Correct 153 ms 312148 KB Output is correct
81 Correct 186 ms 313936 KB Output is correct
82 Correct 143 ms 310728 KB Output is correct
83 Correct 165 ms 312152 KB Output is correct
84 Correct 169 ms 313220 KB Output is correct
85 Correct 154 ms 310692 KB Output is correct
86 Incorrect 170 ms 313172 KB Output isn't correct
87 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 310376 KB Output is correct
2 Correct 152 ms 310416 KB Output is correct
3 Correct 154 ms 311468 KB Output is correct
4 Correct 146 ms 311380 KB Output is correct
5 Correct 144 ms 311488 KB Output is correct
6 Correct 152 ms 311464 KB Output is correct
7 Correct 149 ms 311480 KB Output is correct
8 Correct 149 ms 311012 KB Output is correct
9 Correct 143 ms 310384 KB Output is correct
10 Correct 142 ms 310908 KB Output is correct
11 Correct 148 ms 311380 KB Output is correct
12 Correct 149 ms 311520 KB Output is correct
13 Correct 159 ms 310388 KB Output is correct
14 Correct 145 ms 311512 KB Output is correct
15 Correct 147 ms 310360 KB Output is correct
16 Correct 153 ms 311484 KB Output is correct
17 Correct 164 ms 310356 KB Output is correct
18 Correct 151 ms 311380 KB Output is correct
19 Correct 154 ms 310936 KB Output is correct
20 Correct 148 ms 311040 KB Output is correct
21 Correct 146 ms 311112 KB Output is correct
22 Correct 148 ms 310860 KB Output is correct
23 Correct 151 ms 311492 KB Output is correct
24 Correct 145 ms 310840 KB Output is correct
25 Correct 159 ms 311636 KB Output is correct
26 Correct 151 ms 311572 KB Output is correct
27 Correct 162 ms 311376 KB Output is correct
28 Correct 162 ms 311516 KB Output is correct
29 Correct 151 ms 311408 KB Output is correct
30 Correct 156 ms 311572 KB Output is correct
31 Correct 151 ms 311472 KB Output is correct
32 Correct 156 ms 311648 KB Output is correct
33 Correct 154 ms 311660 KB Output is correct
34 Correct 161 ms 311636 KB Output is correct
35 Correct 152 ms 311068 KB Output is correct
36 Correct 149 ms 310868 KB Output is correct
37 Correct 159 ms 311220 KB Output is correct
38 Correct 148 ms 310820 KB Output is correct
39 Correct 144 ms 310592 KB Output is correct
40 Correct 150 ms 312008 KB Output is correct
41 Correct 144 ms 310608 KB Output is correct
42 Correct 155 ms 311940 KB Output is correct
43 Correct 159 ms 311936 KB Output is correct
44 Correct 144 ms 310456 KB Output is correct
45 Correct 367 ms 332116 KB Output is correct
46 Correct 241 ms 324216 KB Output is correct
47 Correct 456 ms 332136 KB Output is correct
48 Correct 395 ms 332080 KB Output is correct
49 Correct 196 ms 321420 KB Output is correct
50 Correct 355 ms 337260 KB Output is correct
51 Correct 388 ms 332132 KB Output is correct
52 Correct 205 ms 321620 KB Output is correct
53 Correct 192 ms 321548 KB Output is correct
54 Correct 158 ms 316324 KB Output is correct
55 Correct 410 ms 337428 KB Output is correct
56 Correct 189 ms 318808 KB Output is correct
57 Correct 201 ms 321472 KB Output is correct
58 Correct 242 ms 324080 KB Output is correct
59 Correct 180 ms 318764 KB Output is correct
60 Correct 177 ms 318960 KB Output is correct
61 Correct 224 ms 324264 KB Output is correct
62 Correct 205 ms 321532 KB Output is correct
63 Correct 292 ms 325456 KB Output is correct
64 Correct 185 ms 318836 KB Output is correct
65 Correct 324 ms 328276 KB Output is correct
66 Correct 220 ms 321616 KB Output is correct
67 Correct 301 ms 325344 KB Output is correct
68 Correct 322 ms 327532 KB Output is correct
69 Correct 327 ms 328152 KB Output is correct
70 Correct 222 ms 321564 KB Output is correct
71 Correct 317 ms 327388 KB Output is correct
72 Correct 269 ms 325120 KB Output is correct
73 Correct 363 ms 329728 KB Output is correct
74 Correct 209 ms 321420 KB Output is correct
75 Correct 218 ms 318456 KB Output is correct
76 Correct 275 ms 325064 KB Output is correct
77 Correct 369 ms 329808 KB Output is correct
78 Correct 230 ms 320104 KB Output is correct
79 Correct 206 ms 318348 KB Output is correct
80 Correct 173 ms 314420 KB Output is correct
81 Correct 229 ms 319968 KB Output is correct
82 Correct 303 ms 326744 KB Output is correct
83 Correct 183 ms 314448 KB Output is correct
84 Incorrect 322 ms 326780 KB Output isn't correct
85 Halted 0 ms 0 KB -