# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
129160 | 2019-07-11T18:27:22 Z | Vardanyan | Political Development (BOI17_politicaldevelopment) | C++14 | 3000 ms | 16756 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2808 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 49 ms | 3192 KB | Output is correct |
4 | Correct | 23 ms | 3192 KB | Output is correct |
5 | Correct | 23 ms | 3192 KB | Output is correct |
6 | Correct | 22 ms | 3192 KB | Output is correct |
7 | Correct | 22 ms | 3192 KB | Output is correct |
8 | Correct | 4 ms | 2680 KB | Output is correct |
9 | Correct | 4 ms | 2680 KB | Output is correct |
10 | Correct | 4 ms | 2680 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2808 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 49 ms | 3192 KB | Output is correct |
4 | Correct | 23 ms | 3192 KB | Output is correct |
5 | Correct | 23 ms | 3192 KB | Output is correct |
6 | Correct | 22 ms | 3192 KB | Output is correct |
7 | Correct | 22 ms | 3192 KB | Output is correct |
8 | Correct | 4 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 | 23 ms | 3196 KB | Output is correct |
12 | Correct | 22 ms | 3192 KB | Output is correct |
13 | Correct | 4 ms | 2680 KB | Output is correct |
14 | Correct | 23 ms | 3192 KB | Output is correct |
15 | Correct | 4 ms | 2680 KB | Output is correct |
16 | Correct | 24 ms | 3200 KB | Output is correct |
17 | Correct | 4 ms | 2684 KB | Output is correct |
18 | Correct | 23 ms | 3192 KB | Output is correct |
19 | Correct | 4 ms | 2680 KB | Output is correct |
20 | Correct | 10 ms | 2936 KB | Output is correct |
21 | Correct | 10 ms | 2936 KB | Output is correct |
22 | Correct | 4 ms | 2680 KB | Output is correct |
23 | Correct | 27 ms | 3192 KB | Output is correct |
24 | Correct | 4 ms | 2684 KB | Output is correct |
25 | Correct | 27 ms | 3324 KB | Output is correct |
26 | Correct | 24 ms | 3320 KB | Output is correct |
27 | Correct | 14 ms | 3192 KB | Output is correct |
28 | Correct | 24 ms | 3264 KB | Output is correct |
29 | Correct | 13 ms | 3192 KB | Output is correct |
30 | Correct | 25 ms | 3348 KB | Output is correct |
31 | Correct | 25 ms | 3320 KB | Output is correct |
32 | Correct | 26 ms | 3320 KB | Output is correct |
33 | Correct | 25 ms | 3348 KB | Output is correct |
34 | Correct | 26 ms | 3320 KB | Output is correct |
35 | Correct | 10 ms | 3064 KB | Output is correct |
36 | Correct | 10 ms | 2936 KB | Output is correct |
37 | Correct | 9 ms | 3068 KB | Output is correct |
38 | Correct | 6 ms | 2936 KB | Output is correct |
39 | Correct | 6 ms | 2936 KB | Output is correct |
40 | Correct | 61 ms | 3704 KB | Output is correct |
41 | Correct | 6 ms | 2936 KB | Output is correct |
42 | Correct | 60 ms | 3676 KB | Output is correct |
43 | Correct | 64 ms | 3576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2808 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 49 ms | 3192 KB | Output is correct |
4 | Correct | 23 ms | 3192 KB | Output is correct |
5 | Correct | 23 ms | 3192 KB | Output is correct |
6 | Correct | 22 ms | 3192 KB | Output is correct |
7 | Correct | 22 ms | 3192 KB | Output is correct |
8 | Correct | 4 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 | 23 ms | 3196 KB | Output is correct |
12 | Correct | 22 ms | 3192 KB | Output is correct |
13 | Correct | 4 ms | 2680 KB | Output is correct |
14 | Correct | 23 ms | 3192 KB | Output is correct |
15 | Correct | 4 ms | 2680 KB | Output is correct |
16 | Correct | 24 ms | 3200 KB | Output is correct |
17 | Correct | 4 ms | 2684 KB | Output is correct |
18 | Correct | 23 ms | 3192 KB | Output is correct |
19 | Correct | 4 ms | 2680 KB | Output is correct |
20 | Correct | 10 ms | 2936 KB | Output is correct |
21 | Correct | 10 ms | 2936 KB | Output is correct |
22 | Correct | 4 ms | 2680 KB | Output is correct |
23 | Correct | 27 ms | 3192 KB | Output is correct |
24 | Correct | 4 ms | 2684 KB | Output is correct |
25 | Correct | 27 ms | 3324 KB | Output is correct |
26 | Correct | 24 ms | 3320 KB | Output is correct |
27 | Correct | 14 ms | 3192 KB | Output is correct |
28 | Correct | 24 ms | 3264 KB | Output is correct |
29 | Correct | 13 ms | 3192 KB | Output is correct |
30 | Correct | 25 ms | 3348 KB | Output is correct |
31 | Correct | 25 ms | 3320 KB | Output is correct |
32 | Correct | 26 ms | 3320 KB | Output is correct |
33 | Correct | 25 ms | 3348 KB | Output is correct |
34 | Correct | 26 ms | 3320 KB | Output is correct |
35 | Correct | 10 ms | 3064 KB | Output is correct |
36 | Correct | 10 ms | 2936 KB | Output is correct |
37 | Correct | 9 ms | 3068 KB | Output is correct |
38 | Correct | 6 ms | 2936 KB | Output is correct |
39 | Correct | 6 ms | 2936 KB | Output is correct |
40 | Correct | 61 ms | 3704 KB | Output is correct |
41 | Correct | 6 ms | 2936 KB | Output is correct |
42 | Correct | 60 ms | 3676 KB | Output is correct |
43 | Correct | 64 ms | 3576 KB | Output is correct |
44 | Correct | 141 ms | 4600 KB | Output is correct |
45 | Correct | 5 ms | 2680 KB | Output is correct |
46 | Correct | 43 ms | 3552 KB | Output is correct |
47 | Incorrect | 68 ms | 4616 KB | Output isn't correct |
48 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2808 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 49 ms | 3192 KB | Output is correct |
4 | Correct | 23 ms | 3192 KB | Output is correct |
5 | Correct | 23 ms | 3192 KB | Output is correct |
6 | Correct | 22 ms | 3192 KB | Output is correct |
7 | Correct | 22 ms | 3192 KB | Output is correct |
8 | Correct | 4 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 | 23 ms | 3196 KB | Output is correct |
12 | Correct | 22 ms | 3192 KB | Output is correct |
13 | Correct | 4 ms | 2680 KB | Output is correct |
14 | Correct | 23 ms | 3192 KB | Output is correct |
15 | Correct | 4 ms | 2680 KB | Output is correct |
16 | Correct | 24 ms | 3200 KB | Output is correct |
17 | Correct | 4 ms | 2684 KB | Output is correct |
18 | Correct | 23 ms | 3192 KB | Output is correct |
19 | Correct | 4 ms | 2680 KB | Output is correct |
20 | Correct | 10 ms | 2936 KB | Output is correct |
21 | Correct | 10 ms | 2936 KB | Output is correct |
22 | Correct | 4 ms | 2680 KB | Output is correct |
23 | Correct | 27 ms | 3192 KB | Output is correct |
24 | Correct | 4 ms | 2684 KB | Output is correct |
25 | Correct | 27 ms | 3324 KB | Output is correct |
26 | Correct | 24 ms | 3320 KB | Output is correct |
27 | Correct | 14 ms | 3192 KB | Output is correct |
28 | Correct | 24 ms | 3264 KB | Output is correct |
29 | Correct | 13 ms | 3192 KB | Output is correct |
30 | Correct | 25 ms | 3348 KB | Output is correct |
31 | Correct | 25 ms | 3320 KB | Output is correct |
32 | Correct | 26 ms | 3320 KB | Output is correct |
33 | Correct | 25 ms | 3348 KB | Output is correct |
34 | Correct | 26 ms | 3320 KB | Output is correct |
35 | Correct | 10 ms | 3064 KB | Output is correct |
36 | Correct | 10 ms | 2936 KB | Output is correct |
37 | Correct | 9 ms | 3068 KB | Output is correct |
38 | Correct | 6 ms | 2936 KB | Output is correct |
39 | Correct | 6 ms | 2936 KB | Output is correct |
40 | Correct | 61 ms | 3704 KB | Output is correct |
41 | Correct | 6 ms | 2936 KB | Output is correct |
42 | Correct | 60 ms | 3676 KB | Output is correct |
43 | Correct | 64 ms | 3576 KB | Output is correct |
44 | Correct | 5 ms | 2680 KB | Output is correct |
45 | Execution timed out | 3035 ms | 16756 KB | Time limit exceeded |
46 | Halted | 0 ms | 0 KB | - |