# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
129159 | 2019-07-11T18:26:17 Z | Vardanyan | Political Development (BOI17_politicaldevelopment) | C++14 | 3000 ms | 16880 KB |
#include <bits/stdc++.h> using namespace std; const int N = 50*1000+5; set<int> g[N]; int dp[(1<<11)]; int main(){ ios_base::sync_with_stdio(false); int n,k; cin>>n>>k; int x; for(int i = 0;i<n;i++){ int q; cin>>q; while(q--){ int x; cin>>x; g[i].insert(x); } } int anss = 1; while(1){ int id = -1; int sz = 0; for(int i = 0;i<n;i++){ sz = max(sz,(int)g[i].size()); if(g[i].size()<k && g[i].size()){ id = i; // break; } } if(id == -1) break; /*if(sz == 1){ anss = max(anss,sz+1); break; }*/ if(sz == 0) break; vector<int> v; set<int>::iterator it; int ans = 1; for(it = g[id].begin();it!=g[id].end();it++){ int to = *it; v.push_back(to); dp[(1<<(v.size()-1))] = 1; anss = max(anss,2); } for(int i = 1;i<(1<<v.size());i++){ if(!dp[i]) continue; for(int j = 0;j<v.size();j++){ if((i>>j)&1) continue; bool f = true; for(int ii = 0;ii<v.size();ii++){ if((i>>ii)&1){ if(g[v[ii]].find(v[j])==g[v[ii]].end()){ f = false; break; } } } if(f){ dp[i|(1<<j)] = dp[i]+1; ans = max(ans,dp[i]+1); } } } anss = max(ans+1,anss); // cout<<ans<<endl; for(int i = 0;i<v.size();i++){ g[v[i]].erase(g[v[i]].find(id)); g[id].erase(g[id].find(v[i])); } //if(ans == 1) break; } cout<<anss<<endl; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 69 ms | 3192 KB | Output is correct |
4 | Correct | 48 ms | 3184 KB | Output is correct |
5 | Correct | 46 ms | 3192 KB | Output is correct |
6 | Correct | 48 ms | 3192 KB | Output is correct |
7 | Correct | 48 ms | 3192 KB | Output is correct |
8 | Correct | 5 ms | 2680 KB | Output is correct |
9 | Correct | 4 ms | 2680 KB | Output is correct |
10 | Correct | 4 ms | 2680 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 69 ms | 3192 KB | Output is correct |
4 | Correct | 48 ms | 3184 KB | Output is correct |
5 | Correct | 46 ms | 3192 KB | Output is correct |
6 | Correct | 48 ms | 3192 KB | Output is correct |
7 | Correct | 48 ms | 3192 KB | Output is correct |
8 | Correct | 5 ms | 2680 KB | Output is correct |
9 | Correct | 4 ms | 2680 KB | Output is correct |
10 | Correct | 4 ms | 2680 KB | Output is correct |
11 | Correct | 45 ms | 3192 KB | Output is correct |
12 | Correct | 47 ms | 3192 KB | Output is correct |
13 | Correct | 4 ms | 2680 KB | Output is correct |
14 | Correct | 45 ms | 3192 KB | Output is correct |
15 | Correct | 4 ms | 2680 KB | Output is correct |
16 | Correct | 49 ms | 3192 KB | Output is correct |
17 | Correct | 4 ms | 2680 KB | Output is correct |
18 | Correct | 46 ms | 3192 KB | Output is correct |
19 | Correct | 4 ms | 2680 KB | Output is correct |
20 | Correct | 33 ms | 2940 KB | Output is correct |
21 | Correct | 33 ms | 2936 KB | Output is correct |
22 | Correct | 4 ms | 2680 KB | Output is correct |
23 | Correct | 51 ms | 3320 KB | Output is correct |
24 | Correct | 4 ms | 2680 KB | Output is correct |
25 | Correct | 55 ms | 3448 KB | Output is correct |
26 | Correct | 52 ms | 3320 KB | Output is correct |
27 | Correct | 37 ms | 3292 KB | Output is correct |
28 | Correct | 52 ms | 3324 KB | Output is correct |
29 | Correct | 38 ms | 3192 KB | Output is correct |
30 | Correct | 52 ms | 3448 KB | Output is correct |
31 | Correct | 51 ms | 3320 KB | Output is correct |
32 | Correct | 50 ms | 3448 KB | Output is correct |
33 | Correct | 54 ms | 3448 KB | Output is correct |
34 | Correct | 51 ms | 3424 KB | Output is correct |
35 | Correct | 15 ms | 3064 KB | Output is correct |
36 | Correct | 16 ms | 3064 KB | Output is correct |
37 | Correct | 15 ms | 3064 KB | Output is correct |
38 | Correct | 8 ms | 2936 KB | Output is correct |
39 | Correct | 8 ms | 2936 KB | Output is correct |
40 | Correct | 84 ms | 3704 KB | Output is correct |
41 | Correct | 8 ms | 2936 KB | Output is correct |
42 | Correct | 87 ms | 3832 KB | Output is correct |
43 | Correct | 85 ms | 3704 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2684 KB | Output is correct |
2 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 69 ms | 3192 KB | Output is correct |
4 | Correct | 48 ms | 3184 KB | Output is correct |
5 | Correct | 46 ms | 3192 KB | Output is correct |
6 | Correct | 48 ms | 3192 KB | Output is correct |
7 | Correct | 48 ms | 3192 KB | Output is correct |
8 | Correct | 5 ms | 2680 KB | Output is correct |
9 | Correct | 4 ms | 2680 KB | Output is correct |
10 | Correct | 4 ms | 2680 KB | Output is correct |
11 | Correct | 45 ms | 3192 KB | Output is correct |
12 | Correct | 47 ms | 3192 KB | Output is correct |
13 | Correct | 4 ms | 2680 KB | Output is correct |
14 | Correct | 45 ms | 3192 KB | Output is correct |
15 | Correct | 4 ms | 2680 KB | Output is correct |
16 | Correct | 49 ms | 3192 KB | Output is correct |
17 | Correct | 4 ms | 2680 KB | Output is correct |
18 | Correct | 46 ms | 3192 KB | Output is correct |
19 | Correct | 4 ms | 2680 KB | Output is correct |
20 | Correct | 33 ms | 2940 KB | Output is correct |
21 | Correct | 33 ms | 2936 KB | Output is correct |
22 | Correct | 4 ms | 2680 KB | Output is correct |
23 | Correct | 51 ms | 3320 KB | Output is correct |
24 | Correct | 4 ms | 2680 KB | Output is correct |
25 | Correct | 55 ms | 3448 KB | Output is correct |
26 | Correct | 52 ms | 3320 KB | Output is correct |
27 | Correct | 37 ms | 3292 KB | Output is correct |
28 | Correct | 52 ms | 3324 KB | Output is correct |
29 | Correct | 38 ms | 3192 KB | Output is correct |
30 | Correct | 52 ms | 3448 KB | Output is correct |
31 | Correct | 51 ms | 3320 KB | Output is correct |
32 | Correct | 50 ms | 3448 KB | Output is correct |
33 | Correct | 54 ms | 3448 KB | Output is correct |
34 | Correct | 51 ms | 3424 KB | Output is correct |
35 | Correct | 15 ms | 3064 KB | Output is correct |
36 | Correct | 16 ms | 3064 KB | Output is correct |
37 | Correct | 15 ms | 3064 KB | Output is correct |
38 | Correct | 8 ms | 2936 KB | Output is correct |
39 | Correct | 8 ms | 2936 KB | Output is correct |
40 | Correct | 84 ms | 3704 KB | Output is correct |
41 | Correct | 8 ms | 2936 KB | Output is correct |
42 | Correct | 87 ms | 3832 KB | Output is correct |
43 | Correct | 85 ms | 3704 KB | Output is correct |
44 | Correct | 161 ms | 4740 KB | Output is correct |
45 | Correct | 4 ms | 2680 KB | Output is correct |
46 | Correct | 65 ms | 3704 KB | Output is correct |
47 | Incorrect | 93 ms | 4732 KB | Output isn't correct |
48 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 69 ms | 3192 KB | Output is correct |
4 | Correct | 48 ms | 3184 KB | Output is correct |
5 | Correct | 46 ms | 3192 KB | Output is correct |
6 | Correct | 48 ms | 3192 KB | Output is correct |
7 | Correct | 48 ms | 3192 KB | Output is correct |
8 | Correct | 5 ms | 2680 KB | Output is correct |
9 | Correct | 4 ms | 2680 KB | Output is correct |
10 | Correct | 4 ms | 2680 KB | Output is correct |
11 | Correct | 45 ms | 3192 KB | Output is correct |
12 | Correct | 47 ms | 3192 KB | Output is correct |
13 | Correct | 4 ms | 2680 KB | Output is correct |
14 | Correct | 45 ms | 3192 KB | Output is correct |
15 | Correct | 4 ms | 2680 KB | Output is correct |
16 | Correct | 49 ms | 3192 KB | Output is correct |
17 | Correct | 4 ms | 2680 KB | Output is correct |
18 | Correct | 46 ms | 3192 KB | Output is correct |
19 | Correct | 4 ms | 2680 KB | Output is correct |
20 | Correct | 33 ms | 2940 KB | Output is correct |
21 | Correct | 33 ms | 2936 KB | Output is correct |
22 | Correct | 4 ms | 2680 KB | Output is correct |
23 | Correct | 51 ms | 3320 KB | Output is correct |
24 | Correct | 4 ms | 2680 KB | Output is correct |
25 | Correct | 55 ms | 3448 KB | Output is correct |
26 | Correct | 52 ms | 3320 KB | Output is correct |
27 | Correct | 37 ms | 3292 KB | Output is correct |
28 | Correct | 52 ms | 3324 KB | Output is correct |
29 | Correct | 38 ms | 3192 KB | Output is correct |
30 | Correct | 52 ms | 3448 KB | Output is correct |
31 | Correct | 51 ms | 3320 KB | Output is correct |
32 | Correct | 50 ms | 3448 KB | Output is correct |
33 | Correct | 54 ms | 3448 KB | Output is correct |
34 | Correct | 51 ms | 3424 KB | Output is correct |
35 | Correct | 15 ms | 3064 KB | Output is correct |
36 | Correct | 16 ms | 3064 KB | Output is correct |
37 | Correct | 15 ms | 3064 KB | Output is correct |
38 | Correct | 8 ms | 2936 KB | Output is correct |
39 | Correct | 8 ms | 2936 KB | Output is correct |
40 | Correct | 84 ms | 3704 KB | Output is correct |
41 | Correct | 8 ms | 2936 KB | Output is correct |
42 | Correct | 87 ms | 3832 KB | Output is correct |
43 | Correct | 85 ms | 3704 KB | Output is correct |
44 | Correct | 5 ms | 2680 KB | Output is correct |
45 | Execution timed out | 3033 ms | 16880 KB | Time limit exceeded |
46 | Halted | 0 ms | 0 KB | - |