oj.uz

답안 #803045

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
803045 2023-08-02T20:11:53 Z YassineBenYounes Political Development (BOI17_politicaldevelopment) C++17
100 / 100
 802 ms 307720 KB 
#include<bits/stdc++.h>
typedef long long ll;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void init()':
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("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:22:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 22 ms 22292 KB Output is correct
4 Correct 20 ms 21612 KB Output is correct
5 Correct 19 ms 21552 KB Output is correct
6 Correct 21 ms 21640 KB Output is correct
7 Correct 21 ms 21680 KB Output is correct
8 Correct 7 ms 1492 KB Output is correct
9 Correct 1 ms 1504 KB Output is correct
10 Correct 7 ms 1596 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 22 ms 22292 KB Output is correct
4 Correct 20 ms 21612 KB Output is correct
5 Correct 19 ms 21552 KB Output is correct
6 Correct 21 ms 21640 KB Output is correct
7 Correct 21 ms 21680 KB Output is correct
8 Correct 7 ms 1492 KB Output is correct
9 Correct 1 ms 1504 KB Output is correct
10 Correct 7 ms 1596 KB Output is correct
11 Correct 20 ms 21624 KB Output is correct
12 Correct 22 ms 21596 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 20 ms 21532 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 21 ms 21588 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 26 ms 21716 KB Output is correct
19 Correct 7 ms 1588 KB Output is correct
20 Correct 22 ms 21636 KB Output is correct
21 Correct 18 ms 21588 KB Output is correct
22 Correct 7 ms 1624 KB Output is correct
23 Correct 25 ms 22780 KB Output is correct
24 Correct 7 ms 1600 KB Output is correct
25 Correct 24 ms 22740 KB Output is correct
26 Correct 24 ms 22000 KB Output is correct
27 Correct 23 ms 22612 KB Output is correct
28 Correct 24 ms 21844 KB Output is correct
29 Correct 23 ms 22612 KB Output is correct
30 Correct 24 ms 22356 KB Output is correct
31 Correct 25 ms 22900 KB Output is correct
32 Correct 24 ms 22484 KB Output is correct
33 Correct 25 ms 22840 KB Output is correct
34 Correct 25 ms 22868 KB Output is correct
35 Correct 12 ms 11928 KB Output is correct
36 Correct 12 ms 11860 KB Output is correct
37 Correct 12 ms 11860 KB Output is correct
38 Correct 7 ms 6484 KB Output is correct
39 Correct 7 ms 6484 KB Output is correct
40 Correct 30 ms 23352 KB Output is correct
41 Correct 7 ms 6484 KB Output is correct
42 Correct 31 ms 23300 KB Output is correct
43 Correct 30 ms 23252 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1492 KB Output is correct
2 Correct 1 ms 1620 KB Output is correct
3 Correct 2 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 1620 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 785 ms 307548 KB Output is correct
12 Correct 1 ms 1620 KB Output is correct
13 Correct 789 ms 307572 KB Output is correct
14 Correct 1 ms 1620 KB Output is correct
15 Correct 790 ms 307564 KB Output is correct
16 Correct 792 ms 307628 KB Output is correct
17 Correct 802 ms 307648 KB Output is correct
18 Correct 794 ms 307688 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 22 ms 22292 KB Output is correct
4 Correct 20 ms 21612 KB Output is correct
5 Correct 19 ms 21552 KB Output is correct
6 Correct 21 ms 21640 KB Output is correct
7 Correct 21 ms 21680 KB Output is correct
8 Correct 7 ms 1492 KB Output is correct
9 Correct 1 ms 1504 KB Output is correct
10 Correct 7 ms 1596 KB Output is correct
11 Correct 20 ms 21624 KB Output is correct
12 Correct 22 ms 21596 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 20 ms 21532 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 21 ms 21588 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 26 ms 21716 KB Output is correct
19 Correct 7 ms 1588 KB Output is correct
20 Correct 22 ms 21636 KB Output is correct
21 Correct 18 ms 21588 KB Output is correct
22 Correct 7 ms 1624 KB Output is correct
23 Correct 25 ms 22780 KB Output is correct
24 Correct 7 ms 1600 KB Output is correct
25 Correct 24 ms 22740 KB Output is correct
26 Correct 24 ms 22000 KB Output is correct
27 Correct 23 ms 22612 KB Output is correct
28 Correct 24 ms 21844 KB Output is correct
29 Correct 23 ms 22612 KB Output is correct
30 Correct 24 ms 22356 KB Output is correct
31 Correct 25 ms 22900 KB Output is correct
32 Correct 24 ms 22484 KB Output is correct
33 Correct 25 ms 22840 KB Output is correct
34 Correct 25 ms 22868 KB Output is correct
35 Correct 12 ms 11928 KB Output is correct
36 Correct 12 ms 11860 KB Output is correct
37 Correct 12 ms 11860 KB Output is correct
38 Correct 7 ms 6484 KB Output is correct
39 Correct 7 ms 6484 KB Output is correct
40 Correct 30 ms 23352 KB Output is correct
41 Correct 7 ms 6484 KB Output is correct
42 Correct 31 ms 23300 KB Output is correct
43 Correct 30 ms 23252 KB Output is correct
44 Correct 18 ms 24020 KB Output is correct
45 Correct 1 ms 1620 KB Output is correct
46 Correct 31 ms 23184 KB Output is correct
47 Correct 56 ms 23996 KB Output is correct
48 Correct 32 ms 23008 KB Output is correct
49 Correct 51 ms 23888 KB Output is correct
50 Correct 51 ms 23864 KB Output is correct
51 Correct 98 ms 24304 KB Output is correct
52 Correct 21 ms 21620 KB Output is correct
53 Correct 85 ms 24156 KB Output is correct
54 Correct 20 ms 24404 KB Output is correct
55 Correct 27 ms 21768 KB Output is correct
56 Correct 22 ms 21588 KB Output is correct
57 Correct 9 ms 1596 KB Output is correct
58 Correct 87 ms 24096 KB Output is correct
59 Correct 75 ms 23600 KB Output is correct
60 Correct 22 ms 21572 KB Output is correct
61 Correct 74 ms 23508 KB Output is correct
62 Correct 75 ms 23416 KB Output is correct
63 Correct 134 ms 24124 KB Output is correct
64 Correct 490 ms 24020 KB Output is correct
65 Correct 30 ms 23124 KB Output is correct
66 Correct 74 ms 23464 KB Output is correct
67 Correct 18 ms 24024 KB Output is correct
68 Correct 497 ms 23976 KB Output is correct
69 Correct 30 ms 23072 KB Output is correct
70 Correct 73 ms 23848 KB Output is correct
71 Correct 28 ms 23892 KB Output is correct
72 Correct 191 ms 24020 KB Output is correct
73 Correct 22 ms 22448 KB Output is correct
74 Correct 72 ms 23856 KB Output is correct
75 Correct 169 ms 24020 KB Output is correct
76 Correct 37 ms 23484 KB Output is correct
77 Correct 66 ms 24148 KB Output is correct
78 Correct 23 ms 22648 KB Output is correct
79 Correct 30 ms 12116 KB Output is correct
80 Correct 37 ms 23380 KB Output is correct
81 Correct 68 ms 24136 KB Output is correct
82 Correct 7 ms 6628 KB Output is correct
83 Correct 34 ms 12252 KB Output is correct
84 Correct 55 ms 24084 KB Output is correct
85 Correct 7 ms 6528 KB Output is correct
86 Correct 56 ms 24208 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 22 ms 22292 KB Output is correct
4 Correct 20 ms 21612 KB Output is correct
5 Correct 19 ms 21552 KB Output is correct
6 Correct 21 ms 21640 KB Output is correct
7 Correct 21 ms 21680 KB Output is correct
8 Correct 7 ms 1492 KB Output is correct
9 Correct 1 ms 1504 KB Output is correct
10 Correct 7 ms 1596 KB Output is correct
11 Correct 20 ms 21624 KB Output is correct
12 Correct 22 ms 21596 KB Output is correct
13 Correct 1 ms 1492 KB Output is correct
14 Correct 20 ms 21532 KB Output is correct
15 Correct 1 ms 1492 KB Output is correct
16 Correct 21 ms 21588 KB Output is correct
17 Correct 1 ms 1492 KB Output is correct
18 Correct 26 ms 21716 KB Output is correct
19 Correct 7 ms 1588 KB Output is correct
20 Correct 22 ms 21636 KB Output is correct
21 Correct 18 ms 21588 KB Output is correct
22 Correct 7 ms 1624 KB Output is correct
23 Correct 25 ms 22780 KB Output is correct
24 Correct 7 ms 1600 KB Output is correct
25 Correct 24 ms 22740 KB Output is correct
26 Correct 24 ms 22000 KB Output is correct
27 Correct 23 ms 22612 KB Output is correct
28 Correct 24 ms 21844 KB Output is correct
29 Correct 23 ms 22612 KB Output is correct
30 Correct 24 ms 22356 KB Output is correct
31 Correct 25 ms 22900 KB Output is correct
32 Correct 24 ms 22484 KB Output is correct
33 Correct 25 ms 22840 KB Output is correct
34 Correct 25 ms 22868 KB Output is correct
35 Correct 12 ms 11928 KB Output is correct
36 Correct 12 ms 11860 KB Output is correct
37 Correct 12 ms 11860 KB Output is correct
38 Correct 7 ms 6484 KB Output is correct
39 Correct 7 ms 6484 KB Output is correct
40 Correct 30 ms 23352 KB Output is correct
41 Correct 7 ms 6484 KB Output is correct
42 Correct 31 ms 23300 KB Output is correct
43 Correct 30 ms 23252 KB Output is correct
44 Correct 1 ms 1620 KB Output is correct
45 Correct 577 ms 302156 KB Output is correct
46 Correct 348 ms 275016 KB Output is correct
47 Correct 574 ms 301032 KB Output is correct
48 Correct 597 ms 302304 KB Output is correct
49 Correct 211 ms 202156 KB Output is correct
50 Correct 554 ms 307640 KB Output is correct
51 Correct 575 ms 300780 KB Output is correct
52 Correct 236 ms 188928 KB Output is correct
53 Correct 211 ms 202124 KB Output is correct
54 Correct 64 ms 2068 KB Output is correct
55 Correct 558 ms 307720 KB Output is correct
56 Correct 177 ms 188112 KB Output is correct
57 Correct 223 ms 189640 KB Output is correct
58 Correct 572 ms 288724 KB Output is correct
59 Correct 182 ms 187952 KB Output is correct
60 Correct 186 ms 188132 KB Output is correct
61 Correct 557 ms 288732 KB Output is correct
62 Correct 335 ms 259708 KB Output is correct
63 Correct 396 ms 282476 KB Output is correct
64 Correct 181 ms 188104 KB Output is correct
65 Correct 511 ms 292564 KB Output is correct
66 Correct 329 ms 260812 KB Output is correct
67 Correct 440 ms 282192 KB Output is correct
68 Correct 469 ms 290772 KB Output is correct
69 Correct 513 ms 291692 KB Output is correct
70 Correct 275 ms 260108 KB Output is correct
71 Correct 457 ms 291280 KB Output is correct
72 Correct 355 ms 272912 KB Output is correct
73 Correct 510 ms 303764 KB Output is correct
74 Correct 280 ms 260376 KB Output is correct
75 Correct 190 ms 141764 KB Output is correct
76 Correct 349 ms 265880 KB Output is correct
77 Correct 521 ms 303924 KB Output is correct
78 Correct 238 ms 147404 KB Output is correct
79 Correct 202 ms 142112 KB Output is correct
80 Correct 78 ms 58024 KB Output is correct
81 Correct 233 ms 147308 KB Output is correct
82 Correct 428 ms 299880 KB Output is correct
83 Correct 79 ms 58180 KB Output is correct
84 Correct 440 ms 300020 KB Output is correct