oj.uz

Submission #803042

# Submission time Handle Problem Language Result Execution time Memory
803042 2023-08-02T20:09:13 Z AmirElarbi Political Development (BOI17_politicaldevelopment) C++14
100 / 100
 1058 ms 310348 KB 
#include<bits/stdc++.h>
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pair<ll, ll>, null_type, less<pair<ll,ll>>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
////////////////////Only Clear Code//////////////////////////
void usaco_problem(){
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
}
 
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
 
const int mx = 5e4+5;
const int mxnd = mx*33;
const int LOG = 25;
const ll inf = 1e18;
const ll mod = 1e8;
 
vector<int> graph[mx];
 
int ans = 0;
 
vector<int> cur;
bool done[mx];
int n;

bitset<50005> bg[mx];

void solve(int k, bitset<50005> bs){
    if(ans == 10)return;
	ans = max(ans, k);
    if(k == 9){
        if(bs != 0) ans = 10;
        return;
    }
    ans = max(ans, k);
    if(k == 0){
        for(int i = 0; i < n;i++){ 
            cur.push_back(i);
            done[i] = 1;
            solve(k+1, bg[i]);
            done[i] = 0;
            cur.pop_back();
        }
        return;
    }
	bitset<50005> now = bs;
    while(now != 0){
		long unsigned int to = now._Find_first();
        now[to] = 0;
		solve(k+1, now & bg[to]);
		if(ans == 10) return;
	}
    /*
    for(int adj : graph[cur[0]]){
        if(done[adj])continue;
        bool take = 1;
        for(int x : cur){
            if(mp[x][adj] == 0)take = 0;
        }
        if(take){
            cur.push_back(adj);
            done[adj] = 1;
            solve(k+1);
            done[adj] = 0;
            cur.pop_back();
        }
    }*/
}
 
void run_case(){
    int k;cin >> n >> k;
    for(int i = 0; i < n;i++){
        int c;cin >> c;
        while(c--){
            int x;cin >> x;
            //graph[i].push_back(x);
            bg[i][x] = 1;
        }
    }
    ans = 0;
    solve(0,0);
    cout << ans << endl;
}
 
int main(){
    speed;
    int t = 1;
    //cin >> t;
    while(t--){
        run_case();
    }
}
 
/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message

politicaldevelopment.cpp: In function 'void usaco_problem()':
politicaldevelopment.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void init()':
politicaldevelopment.cpp:18:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:20:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 24 ms 22356 KB Output is correct
4 Correct 23 ms 21588 KB Output is correct
5 Correct 23 ms 21608 KB Output is correct
6 Correct 24 ms 21708 KB Output is correct
7 Correct 23 ms 21740 KB Output is correct
8 Correct 8 ms 1560 KB Output is correct
9 Correct 1 ms 1500 KB Output is correct
10 Correct 8 ms 1644 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 24 ms 22356 KB Output is correct
4 Correct 23 ms 21588 KB Output is correct
5 Correct 23 ms 21608 KB Output is correct
6 Correct 24 ms 21708 KB Output is correct
7 Correct 23 ms 21740 KB Output is correct
8 Correct 8 ms 1560 KB Output is correct
9 Correct 1 ms 1500 KB Output is correct
10 Correct 8 ms 1644 KB Output is correct
11 Correct 22 ms 21680 KB Output is correct
12 Correct 22 ms 21608 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 23 ms 21628 KB Output is correct
15 Correct 1 ms 1496 KB Output is correct
16 Correct 23 ms 21588 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 24 ms 21700 KB Output is correct
19 Correct 8 ms 1492 KB Output is correct
20 Correct 18 ms 21588 KB Output is correct
21 Correct 18 ms 21640 KB Output is correct
22 Correct 8 ms 1620 KB Output is correct
23 Correct 31 ms 22840 KB Output is correct
24 Correct 8 ms 1628 KB Output is correct
25 Correct 27 ms 22740 KB Output is correct
26 Correct 25 ms 22068 KB Output is correct
27 Correct 33 ms 22668 KB Output is correct
28 Correct 28 ms 22008 KB Output is correct
29 Correct 26 ms 22632 KB Output is correct
30 Correct 27 ms 22420 KB Output is correct
31 Correct 28 ms 22868 KB Output is correct
32 Correct 26 ms 22556 KB Output is correct
33 Correct 28 ms 22868 KB Output is correct
34 Correct 30 ms 23144 KB Output is correct
35 Correct 13 ms 11988 KB Output is correct
36 Correct 14 ms 11860 KB Output is correct
37 Correct 14 ms 11912 KB Output is correct
38 Correct 8 ms 6508 KB Output is correct
39 Correct 9 ms 6636 KB Output is correct
40 Correct 35 ms 23436 KB Output is correct
41 Correct 9 ms 6624 KB Output is correct
42 Correct 35 ms 23400 KB Output is correct
43 Correct 35 ms 23380 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1620 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1620 KB Output is correct
4 Correct 1 ms 1620 KB Output is correct
5 Correct 1 ms 1620 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 1632 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1620 KB Output is correct
11 Correct 1058 ms 310212 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 1014 ms 310348 KB Output is correct
14 Correct 1 ms 1620 KB Output is correct
15 Correct 1024 ms 310208 KB Output is correct
16 Correct 992 ms 310248 KB Output is correct
17 Correct 1014 ms 310304 KB Output is correct
18 Correct 998 ms 310348 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 24 ms 22356 KB Output is correct
4 Correct 23 ms 21588 KB Output is correct
5 Correct 23 ms 21608 KB Output is correct
6 Correct 24 ms 21708 KB Output is correct
7 Correct 23 ms 21740 KB Output is correct
8 Correct 8 ms 1560 KB Output is correct
9 Correct 1 ms 1500 KB Output is correct
10 Correct 8 ms 1644 KB Output is correct
11 Correct 22 ms 21680 KB Output is correct
12 Correct 22 ms 21608 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 23 ms 21628 KB Output is correct
15 Correct 1 ms 1496 KB Output is correct
16 Correct 23 ms 21588 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 24 ms 21700 KB Output is correct
19 Correct 8 ms 1492 KB Output is correct
20 Correct 18 ms 21588 KB Output is correct
21 Correct 18 ms 21640 KB Output is correct
22 Correct 8 ms 1620 KB Output is correct
23 Correct 31 ms 22840 KB Output is correct
24 Correct 8 ms 1628 KB Output is correct
25 Correct 27 ms 22740 KB Output is correct
26 Correct 25 ms 22068 KB Output is correct
27 Correct 33 ms 22668 KB Output is correct
28 Correct 28 ms 22008 KB Output is correct
29 Correct 26 ms 22632 KB Output is correct
30 Correct 27 ms 22420 KB Output is correct
31 Correct 28 ms 22868 KB Output is correct
32 Correct 26 ms 22556 KB Output is correct
33 Correct 28 ms 22868 KB Output is correct
34 Correct 30 ms 23144 KB Output is correct
35 Correct 13 ms 11988 KB Output is correct
36 Correct 14 ms 11860 KB Output is correct
37 Correct 14 ms 11912 KB Output is correct
38 Correct 8 ms 6508 KB Output is correct
39 Correct 9 ms 6636 KB Output is correct
40 Correct 35 ms 23436 KB Output is correct
41 Correct 9 ms 6624 KB Output is correct
42 Correct 35 ms 23400 KB Output is correct
43 Correct 35 ms 23380 KB Output is correct
44 Correct 21 ms 24148 KB Output is correct
45 Correct 1 ms 1504 KB Output is correct
46 Correct 37 ms 23188 KB Output is correct
47 Correct 62 ms 24068 KB Output is correct
48 Correct 38 ms 23096 KB Output is correct
49 Correct 61 ms 24020 KB Output is correct
50 Correct 63 ms 24176 KB Output is correct
51 Correct 123 ms 24616 KB Output is correct
52 Correct 24 ms 21668 KB Output is correct
53 Correct 109 ms 24612 KB Output is correct
54 Correct 21 ms 24816 KB Output is correct
55 Correct 30 ms 21720 KB Output is correct
56 Correct 23 ms 21588 KB Output is correct
57 Correct 8 ms 1492 KB Output is correct
58 Correct 114 ms 24532 KB Output is correct
59 Correct 92 ms 23704 KB Output is correct
60 Correct 26 ms 21704 KB Output is correct
61 Correct 94 ms 23636 KB Output is correct
62 Correct 91 ms 23636 KB Output is correct
63 Correct 162 ms 24276 KB Output is correct
64 Correct 662 ms 24204 KB Output is correct
65 Correct 35 ms 23124 KB Output is correct
66 Correct 108 ms 23628 KB Output is correct
67 Correct 18 ms 24148 KB Output is correct
68 Correct 640 ms 24144 KB Output is correct
69 Correct 46 ms 23244 KB Output is correct
70 Correct 88 ms 24004 KB Output is correct
71 Correct 32 ms 24248 KB Output is correct
72 Correct 224 ms 24260 KB Output is correct
73 Correct 26 ms 22520 KB Output is correct
74 Correct 89 ms 24040 KB Output is correct
75 Correct 216 ms 24248 KB Output is correct
76 Correct 43 ms 23700 KB Output is correct
77 Correct 82 ms 24404 KB Output is correct
78 Correct 25 ms 22612 KB Output is correct
79 Correct 35 ms 12372 KB Output is correct
80 Correct 44 ms 23508 KB Output is correct
81 Correct 84 ms 24428 KB Output is correct
82 Correct 8 ms 6612 KB Output is correct
83 Correct 35 ms 12372 KB Output is correct
84 Correct 67 ms 24312 KB Output is correct
85 Correct 8 ms 6636 KB Output is correct
86 Correct 72 ms 24432 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 24 ms 22356 KB Output is correct
4 Correct 23 ms 21588 KB Output is correct
5 Correct 23 ms 21608 KB Output is correct
6 Correct 24 ms 21708 KB Output is correct
7 Correct 23 ms 21740 KB Output is correct
8 Correct 8 ms 1560 KB Output is correct
9 Correct 1 ms 1500 KB Output is correct
10 Correct 8 ms 1644 KB Output is correct
11 Correct 22 ms 21680 KB Output is correct
12 Correct 22 ms 21608 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 23 ms 21628 KB Output is correct
15 Correct 1 ms 1496 KB Output is correct
16 Correct 23 ms 21588 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 24 ms 21700 KB Output is correct
19 Correct 8 ms 1492 KB Output is correct
20 Correct 18 ms 21588 KB Output is correct
21 Correct 18 ms 21640 KB Output is correct
22 Correct 8 ms 1620 KB Output is correct
23 Correct 31 ms 22840 KB Output is correct
24 Correct 8 ms 1628 KB Output is correct
25 Correct 27 ms 22740 KB Output is correct
26 Correct 25 ms 22068 KB Output is correct
27 Correct 33 ms 22668 KB Output is correct
28 Correct 28 ms 22008 KB Output is correct
29 Correct 26 ms 22632 KB Output is correct
30 Correct 27 ms 22420 KB Output is correct
31 Correct 28 ms 22868 KB Output is correct
32 Correct 26 ms 22556 KB Output is correct
33 Correct 28 ms 22868 KB Output is correct
34 Correct 30 ms 23144 KB Output is correct
35 Correct 13 ms 11988 KB Output is correct
36 Correct 14 ms 11860 KB Output is correct
37 Correct 14 ms 11912 KB Output is correct
38 Correct 8 ms 6508 KB Output is correct
39 Correct 9 ms 6636 KB Output is correct
40 Correct 35 ms 23436 KB Output is correct
41 Correct 9 ms 6624 KB Output is correct
42 Correct 35 ms 23400 KB Output is correct
43 Correct 35 ms 23380 KB Output is correct
44 Correct 1 ms 1620 KB Output is correct
45 Correct 751 ms 304016 KB Output is correct
46 Correct 421 ms 275936 KB Output is correct
47 Correct 744 ms 302732 KB Output is correct
48 Correct 779 ms 304096 KB Output is correct
49 Correct 279 ms 202816 KB Output is correct
50 Correct 691 ms 310128 KB Output is correct
51 Correct 723 ms 302492 KB Output is correct
52 Correct 299 ms 189508 KB Output is correct
53 Correct 275 ms 202852 KB Output is correct
54 Correct 70 ms 2252 KB Output is correct
55 Correct 789 ms 310092 KB Output is correct
56 Correct 214 ms 188460 KB Output is correct
57 Correct 273 ms 190384 KB Output is correct
58 Correct 707 ms 289532 KB Output is correct
59 Correct 207 ms 188400 KB Output is correct
60 Correct 219 ms 188396 KB Output is correct
61 Correct 703 ms 289724 KB Output is correct
62 Correct 395 ms 260496 KB Output is correct
63 Correct 481 ms 283632 KB Output is correct
64 Correct 209 ms 188404 KB Output is correct
65 Correct 632 ms 294012 KB Output is correct
66 Correct 388 ms 261484 KB Output is correct
67 Correct 482 ms 283220 KB Output is correct
68 Correct 559 ms 292036 KB Output is correct
69 Correct 645 ms 292972 KB Output is correct
70 Correct 314 ms 260812 KB Output is correct
71 Correct 574 ms 292544 KB Output is correct
72 Correct 427 ms 273988 KB Output is correct
73 Correct 631 ms 305336 KB Output is correct
74 Correct 332 ms 261108 KB Output is correct
75 Correct 234 ms 142348 KB Output is correct
76 Correct 435 ms 266980 KB Output is correct
77 Correct 627 ms 305228 KB Output is correct
78 Correct 330 ms 148236 KB Output is correct
79 Correct 235 ms 142700 KB Output is correct
80 Correct 95 ms 58300 KB Output is correct
81 Correct 289 ms 148064 KB Output is correct
82 Correct 517 ms 301136 KB Output is correct
83 Correct 97 ms 58572 KB Output is correct
84 Correct 524 ms 301284 KB Output is correct