oj.uz

Submission #890576

# Submission time Handle Problem Language Result Execution time Memory
890576 2023-12-21T13:45:54 Z zeta7532 Political Development (BOI17_politicaldevelopment) C++17
100 / 100
 1979 ms 102332 KB 
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

int main() {
    ll N,K;
    cin >> N >> K;
    vector<ll> deg(N,0);
    vector<vector<ll>> G(N);
    vector<map<ll,ll>> M(N);
    rep(i,N){
        cin >> deg[i];
        rep(j,deg[i]){
            ll x;
            cin >> x;
            G[i].push_back(x);
            M[i][x]++;
        }
        M[i][i]++;
    }
    vector<bool> seen(N,false);
    set<pair<ll,ll>> s;
    rep(i,N) s.insert({deg[i],i});
    ll ans=0;
    while(s.size()>0){
        auto it=*s.begin();
        s.erase(it);
        ll i=it.se;
        vector<ll> A;
        rep(j,G[i].size()){
            if(seen[G[i][j]]) continue;
            A.push_back(G[i][j]);
        }
        ll sz=A.size();
        rep(bit,1<<sz){
            vector<ll> B;
            rep(j,sz) if(bit&(1<<j)) B.push_back(A[j]);
            bool ok=true;
            ll sz_B=B.size();
            rep(j,sz_B) rep(k,sz_B) if(M[B[j]][B[k]]==0) ok=false;
            if(ok) ans=max(ans,sz_B);
        }
        seen[i]=true;
        for(ll j:G[i]){
            if(seen[j]) continue;
            s.erase({deg[j],j});
            deg[j]--;
            s.insert({deg[j],j});
        }
    }
    cout << ans+1 << endl;
    return 0;
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:10:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define rep(i,n) for(ll i=0;i<n;i++)
......
   39 |         rep(j,G[i].size()){
      |             ~~~~~~~~~~~~~     
politicaldevelopment.cpp:39:9: note: in expansion of macro 'rep'
   39 |         rep(j,G[i].size()){
      |         ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 ms 2240 KB Output is correct
4 Correct 7 ms 2128 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 ms 2240 KB Output is correct
4 Correct 7 ms 2128 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 7 ms 2140 KB Output is correct
12 Correct 9 ms 2320 KB Output is correct
13 Correct 0 ms 432 KB Output is correct
14 Correct 7 ms 2140 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 8 ms 2140 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 7 ms 2140 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 5 ms 1880 KB Output is correct
21 Correct 4 ms 1884 KB Output is correct
22 Correct 3 ms 1232 KB Output is correct
23 Correct 9 ms 2396 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Correct 9 ms 2648 KB Output is correct
26 Correct 8 ms 2396 KB Output is correct
27 Correct 7 ms 2136 KB Output is correct
28 Correct 8 ms 2396 KB Output is correct
29 Correct 7 ms 2140 KB Output is correct
30 Correct 10 ms 2372 KB Output is correct
31 Correct 9 ms 2560 KB Output is correct
32 Correct 9 ms 2396 KB Output is correct
33 Correct 9 ms 2396 KB Output is correct
34 Correct 9 ms 2396 KB Output is correct
35 Correct 5 ms 1368 KB Output is correct
36 Correct 5 ms 1324 KB Output is correct
37 Correct 5 ms 1368 KB Output is correct
38 Correct 3 ms 1116 KB Output is correct
39 Correct 3 ms 1116 KB Output is correct
40 Correct 14 ms 3164 KB Output is correct
41 Correct 3 ms 1112 KB Output is correct
42 Correct 14 ms 3164 KB Output is correct
43 Correct 14 ms 3264 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1372 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1294 ms 102136 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1253 ms 102324 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1261 ms 102332 KB Output is correct
16 Correct 1258 ms 102116 KB Output is correct
17 Correct 1276 ms 102084 KB Output is correct
18 Correct 1232 ms 102196 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 ms 2240 KB Output is correct
4 Correct 7 ms 2128 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 7 ms 2140 KB Output is correct
12 Correct 9 ms 2320 KB Output is correct
13 Correct 0 ms 432 KB Output is correct
14 Correct 7 ms 2140 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 8 ms 2140 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 7 ms 2140 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 5 ms 1880 KB Output is correct
21 Correct 4 ms 1884 KB Output is correct
22 Correct 3 ms 1232 KB Output is correct
23 Correct 9 ms 2396 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Correct 9 ms 2648 KB Output is correct
26 Correct 8 ms 2396 KB Output is correct
27 Correct 7 ms 2136 KB Output is correct
28 Correct 8 ms 2396 KB Output is correct
29 Correct 7 ms 2140 KB Output is correct
30 Correct 10 ms 2372 KB Output is correct
31 Correct 9 ms 2560 KB Output is correct
32 Correct 9 ms 2396 KB Output is correct
33 Correct 9 ms 2396 KB Output is correct
34 Correct 9 ms 2396 KB Output is correct
35 Correct 5 ms 1368 KB Output is correct
36 Correct 5 ms 1324 KB Output is correct
37 Correct 5 ms 1368 KB Output is correct
38 Correct 3 ms 1116 KB Output is correct
39 Correct 3 ms 1116 KB Output is correct
40 Correct 14 ms 3164 KB Output is correct
41 Correct 3 ms 1112 KB Output is correct
42 Correct 14 ms 3164 KB Output is correct
43 Correct 14 ms 3264 KB Output is correct
44 Correct 112 ms 4536 KB Output is correct
45 Correct 0 ms 344 KB Output is correct
46 Correct 15 ms 3524 KB Output is correct
47 Correct 52 ms 7984 KB Output is correct
48 Correct 20 ms 3248 KB Output is correct
49 Correct 52 ms 7896 KB Output is correct
50 Correct 55 ms 8048 KB Output is correct
51 Correct 845 ms 23840 KB Output is correct
52 Correct 6 ms 2140 KB Output is correct
53 Correct 1884 ms 8588 KB Output is correct
54 Correct 1874 ms 29304 KB Output is correct
55 Correct 7 ms 2136 KB Output is correct
56 Correct 7 ms 2136 KB Output is correct
57 Correct 3 ms 1372 KB Output is correct
58 Correct 1979 ms 8604 KB Output is correct
59 Correct 13 ms 2908 KB Output is correct
60 Correct 7 ms 2140 KB Output is correct
61 Correct 13 ms 2908 KB Output is correct
62 Correct 13 ms 3056 KB Output is correct
63 Correct 107 ms 4444 KB Output is correct
64 Correct 58 ms 4188 KB Output is correct
65 Correct 12 ms 2908 KB Output is correct
66 Correct 13 ms 3060 KB Output is correct
67 Correct 138 ms 10108 KB Output is correct
68 Correct 58 ms 4188 KB Output is correct
69 Correct 13 ms 2908 KB Output is correct
70 Correct 56 ms 6740 KB Output is correct
71 Correct 134 ms 9912 KB Output is correct
72 Correct 99 ms 9548 KB Output is correct
73 Correct 7 ms 2140 KB Output is correct
74 Correct 45 ms 6880 KB Output is correct
75 Correct 101 ms 9648 KB Output is correct
76 Correct 22 ms 4432 KB Output is correct
77 Correct 268 ms 15136 KB Output is correct
78 Correct 7 ms 2144 KB Output is correct
79 Correct 136 ms 7464 KB Output is correct
80 Correct 22 ms 4444 KB Output is correct
81 Correct 269 ms 14932 KB Output is correct
82 Correct 3 ms 1116 KB Output is correct
83 Correct 131 ms 7504 KB Output is correct
84 Correct 104 ms 10396 KB Output is correct
85 Correct 4 ms 1112 KB Output is correct
86 Correct 114 ms 10324 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 ms 2240 KB Output is correct
4 Correct 7 ms 2128 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 7 ms 2140 KB Output is correct
8 Correct 3 ms 1372 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 7 ms 2140 KB Output is correct
12 Correct 9 ms 2320 KB Output is correct
13 Correct 0 ms 432 KB Output is correct
14 Correct 7 ms 2140 KB Output is correct
15 Correct 0 ms 436 KB Output is correct
16 Correct 8 ms 2140 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 7 ms 2140 KB Output is correct
19 Correct 2 ms 1372 KB Output is correct
20 Correct 5 ms 1880 KB Output is correct
21 Correct 4 ms 1884 KB Output is correct
22 Correct 3 ms 1232 KB Output is correct
23 Correct 9 ms 2396 KB Output is correct
24 Correct 3 ms 1372 KB Output is correct
25 Correct 9 ms 2648 KB Output is correct
26 Correct 8 ms 2396 KB Output is correct
27 Correct 7 ms 2136 KB Output is correct
28 Correct 8 ms 2396 KB Output is correct
29 Correct 7 ms 2140 KB Output is correct
30 Correct 10 ms 2372 KB Output is correct
31 Correct 9 ms 2560 KB Output is correct
32 Correct 9 ms 2396 KB Output is correct
33 Correct 9 ms 2396 KB Output is correct
34 Correct 9 ms 2396 KB Output is correct
35 Correct 5 ms 1368 KB Output is correct
36 Correct 5 ms 1324 KB Output is correct
37 Correct 5 ms 1368 KB Output is correct
38 Correct 3 ms 1116 KB Output is correct
39 Correct 3 ms 1116 KB Output is correct
40 Correct 14 ms 3164 KB Output is correct
41 Correct 3 ms 1112 KB Output is correct
42 Correct 14 ms 3164 KB Output is correct
43 Correct 14 ms 3264 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 377 ms 50512 KB Output is correct
46 Correct 130 ms 23048 KB Output is correct
47 Correct 387 ms 51636 KB Output is correct
48 Correct 425 ms 50468 KB Output is correct
49 Correct 82 ms 19504 KB Output is correct
50 Correct 366 ms 41708 KB Output is correct
51 Correct 389 ms 51312 KB Output is correct
52 Correct 72 ms 19320 KB Output is correct
53 Correct 92 ms 19400 KB Output is correct
54 Correct 22 ms 10588 KB Output is correct
55 Correct 363 ms 41788 KB Output is correct
56 Correct 53 ms 15444 KB Output is correct
57 Correct 72 ms 19544 KB Output is correct
58 Correct 103 ms 23292 KB Output is correct
59 Correct 52 ms 15648 KB Output is correct
60 Correct 48 ms 15676 KB Output is correct
61 Correct 109 ms 23168 KB Output is correct
62 Correct 76 ms 19024 KB Output is correct
63 Correct 165 ms 26236 KB Output is correct
64 Correct 51 ms 15452 KB Output is correct
65 Correct 237 ms 34788 KB Output is correct
66 Correct 78 ms 19040 KB Output is correct
67 Correct 168 ms 26436 KB Output is correct
68 Correct 225 ms 33056 KB Output is correct
69 Correct 227 ms 34688 KB Output is correct
70 Correct 87 ms 19048 KB Output is correct
71 Correct 231 ms 33004 KB Output is correct
72 Correct 142 ms 25276 KB Output is correct
73 Correct 282 ms 42088 KB Output is correct
74 Correct 82 ms 18972 KB Output is correct
75 Correct 84 ms 15204 KB Output is correct
76 Correct 142 ms 25296 KB Output is correct
77 Correct 298 ms 42492 KB Output is correct
78 Correct 128 ms 21148 KB Output is correct
79 Correct 77 ms 15184 KB Output is correct
80 Correct 39 ms 7504 KB Output is correct
81 Correct 129 ms 21328 KB Output is correct
82 Correct 191 ms 31180 KB Output is correct
83 Correct 41 ms 7504 KB Output is correct
84 Correct 190 ms 31200 KB Output is correct