# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

162580 | 2019-11-08T20:11:33 Z | MvC | Political Development (BOI17_politicaldevelopment) | C++11 | 837 ms | 29932 KB |

#include <bits/stdc++.h> using namespace std; typedef long long lint; typedef pair<int, int> pi; vector<int> gph[50005]; set<pi> edgs; bool vis[50005]; int deg[50005]; int n; int main(){ scanf("%d %*d",&n); priority_queue<pi, vector<pi>, greater<pi> > pq; for(int i=0; i<n; i++){ scanf("%d",°[i]); gph[i].resize(deg[i]); pq.push(pi(deg[i], i)); for(auto &j : gph[i]){ scanf("%d",&j); edgs.insert(pi(i, j)); } } int ans = 0; while(true){ while(!pq.empty() && vis[pq.top().second]) pq.pop(); if(pq.empty()) break; int w = pq.top().second; vis[w] = 1; deg[w] = 0; pq.pop(); vector<int> v = {w}; for(auto &j : gph[w]){ if(!vis[j]){ deg[j]--; pq.push(pi(deg[j], j)); v.push_back(j); } } vis[w] = 1; bool adj[11][11] = {}; for(int i=0; i<v.size(); i++){ adj[i][i] = 1; for(int j=0; j<v.size(); j++){ if(i != j && edgs.find(pi(v[i], v[j])) != edgs.end()){ adj[i][j] = 1; } } } for(int i=1; i<(1<<v.size()); i+=2){ bool ok = 1; int cnt = 0; for(int j=0; j<v.size(); j++){ if((i >> j) % 2 == 0) continue; cnt++; for(int k=0; k<v.size(); k++){ if((i >> k) % 2 == 0) continue; if(adj[j][k] == 0) ok = 0; } } if(ok) ans = max(ans, cnt); } } cout << ans; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 3 ms | 1528 KB | Output is correct |

2 | Correct | 3 ms | 1528 KB | Output is correct |

3 | Correct | 11 ms | 2168 KB | Output is correct |

4 | Correct | 9 ms | 2168 KB | Output is correct |

5 | Correct | 9 ms | 2168 KB | Output is correct |

6 | Correct | 10 ms | 2168 KB | Output is correct |

7 | Correct | 10 ms | 2168 KB | Output is correct |

8 | Correct | 4 ms | 1656 KB | Output is correct |

9 | Correct | 3 ms | 1528 KB | Output is correct |

10 | Correct | 4 ms | 1660 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 3 ms | 1528 KB | Output is correct |

2 | Correct | 3 ms | 1528 KB | Output is correct |

3 | Correct | 11 ms | 2168 KB | Output is correct |

4 | Correct | 9 ms | 2168 KB | Output is correct |

5 | Correct | 9 ms | 2168 KB | Output is correct |

6 | Correct | 10 ms | 2168 KB | Output is correct |

7 | Correct | 10 ms | 2168 KB | Output is correct |

8 | Correct | 4 ms | 1656 KB | Output is correct |

9 | Correct | 3 ms | 1528 KB | Output is correct |

10 | Correct | 4 ms | 1660 KB | Output is correct |

11 | Correct | 10 ms | 2296 KB | Output is correct |

12 | Correct | 9 ms | 2296 KB | Output is correct |

13 | Correct | 3 ms | 1528 KB | Output is correct |

14 | Correct | 10 ms | 2296 KB | Output is correct |

15 | Correct | 3 ms | 1528 KB | Output is correct |

16 | Correct | 10 ms | 2296 KB | Output is correct |

17 | Correct | 4 ms | 1528 KB | Output is correct |

18 | Correct | 12 ms | 2296 KB | Output is correct |

19 | Correct | 4 ms | 1656 KB | Output is correct |

20 | Correct | 7 ms | 2056 KB | Output is correct |

21 | Correct | 7 ms | 2040 KB | Output is correct |

22 | Correct | 4 ms | 1656 KB | Output is correct |

23 | Correct | 13 ms | 2296 KB | Output is correct |

24 | Correct | 5 ms | 1656 KB | Output is correct |

25 | Correct | 13 ms | 2296 KB | Output is correct |

26 | Correct | 12 ms | 2296 KB | Output is correct |

27 | Correct | 10 ms | 2168 KB | Output is correct |

28 | Correct | 12 ms | 2296 KB | Output is correct |

29 | Correct | 11 ms | 2168 KB | Output is correct |

30 | Correct | 13 ms | 2424 KB | Output is correct |

31 | Correct | 14 ms | 2428 KB | Output is correct |

32 | Correct | 14 ms | 2424 KB | Output is correct |

33 | Correct | 13 ms | 2424 KB | Output is correct |

34 | Correct | 14 ms | 2428 KB | Output is correct |

35 | Correct | 9 ms | 1912 KB | Output is correct |

36 | Correct | 8 ms | 1912 KB | Output is correct |

37 | Correct | 8 ms | 1888 KB | Output is correct |

38 | Correct | 6 ms | 1756 KB | Output is correct |

39 | Correct | 6 ms | 1788 KB | Output is correct |

40 | Correct | 19 ms | 2820 KB | Output is correct |

41 | Correct | 6 ms | 1784 KB | Output is correct |

42 | Correct | 19 ms | 2808 KB | Output is correct |

43 | Correct | 20 ms | 2936 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 4 ms | 1656 KB | Output is correct |

2 | Correct | 3 ms | 1528 KB | Output is correct |

3 | Correct | 3 ms | 1528 KB | Output is correct |

4 | Correct | 3 ms | 1528 KB | Output is correct |

5 | Correct | 3 ms | 1528 KB | Output is correct |

6 | Correct | 3 ms | 1528 KB | Output is correct |

7 | Correct | 3 ms | 1528 KB | Output is correct |

8 | Correct | 3 ms | 1528 KB | Output is correct |

9 | Correct | 3 ms | 1528 KB | Output is correct |

10 | Correct | 3 ms | 1528 KB | Output is correct |

11 | Correct | 802 ms | 28780 KB | Output is correct |

12 | Correct | 3 ms | 1528 KB | Output is correct |

13 | Correct | 807 ms | 29036 KB | Output is correct |

14 | Correct | 3 ms | 1656 KB | Output is correct |

15 | Correct | 809 ms | 29900 KB | Output is correct |

16 | Correct | 830 ms | 29932 KB | Output is correct |

17 | Correct | 824 ms | 29932 KB | Output is correct |

18 | Correct | 837 ms | 29928 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 3 ms | 1528 KB | Output is correct |

2 | Correct | 3 ms | 1528 KB | Output is correct |

3 | Correct | 11 ms | 2168 KB | Output is correct |

4 | Correct | 9 ms | 2168 KB | Output is correct |

5 | Correct | 9 ms | 2168 KB | Output is correct |

6 | Correct | 10 ms | 2168 KB | Output is correct |

7 | Correct | 10 ms | 2168 KB | Output is correct |

8 | Correct | 4 ms | 1656 KB | Output is correct |

9 | Correct | 3 ms | 1528 KB | Output is correct |

10 | Correct | 4 ms | 1660 KB | Output is correct |

11 | Correct | 10 ms | 2296 KB | Output is correct |

12 | Correct | 9 ms | 2296 KB | Output is correct |

13 | Correct | 3 ms | 1528 KB | Output is correct |

14 | Correct | 10 ms | 2296 KB | Output is correct |

15 | Correct | 3 ms | 1528 KB | Output is correct |

16 | Correct | 10 ms | 2296 KB | Output is correct |

17 | Correct | 4 ms | 1528 KB | Output is correct |

18 | Correct | 12 ms | 2296 KB | Output is correct |

19 | Correct | 4 ms | 1656 KB | Output is correct |

20 | Correct | 7 ms | 2056 KB | Output is correct |

21 | Correct | 7 ms | 2040 KB | Output is correct |

22 | Correct | 4 ms | 1656 KB | Output is correct |

23 | Correct | 13 ms | 2296 KB | Output is correct |

24 | Correct | 5 ms | 1656 KB | Output is correct |

25 | Correct | 13 ms | 2296 KB | Output is correct |

26 | Correct | 12 ms | 2296 KB | Output is correct |

27 | Correct | 10 ms | 2168 KB | Output is correct |

28 | Correct | 12 ms | 2296 KB | Output is correct |

29 | Correct | 11 ms | 2168 KB | Output is correct |

30 | Correct | 13 ms | 2424 KB | Output is correct |

31 | Correct | 14 ms | 2428 KB | Output is correct |

32 | Correct | 14 ms | 2424 KB | Output is correct |

33 | Correct | 13 ms | 2424 KB | Output is correct |

34 | Correct | 14 ms | 2428 KB | Output is correct |

35 | Correct | 9 ms | 1912 KB | Output is correct |

36 | Correct | 8 ms | 1912 KB | Output is correct |

37 | Correct | 8 ms | 1888 KB | Output is correct |

38 | Correct | 6 ms | 1756 KB | Output is correct |

39 | Correct | 6 ms | 1788 KB | Output is correct |

40 | Correct | 19 ms | 2820 KB | Output is correct |

41 | Correct | 6 ms | 1784 KB | Output is correct |

42 | Correct | 19 ms | 2808 KB | Output is correct |

43 | Correct | 20 ms | 2936 KB | Output is correct |

44 | Correct | 91 ms | 3704 KB | Output is correct |

45 | Correct | 3 ms | 1528 KB | Output is correct |

46 | Correct | 20 ms | 2808 KB | Output is correct |

47 | Correct | 43 ms | 3960 KB | Output is correct |

48 | Correct | 20 ms | 2936 KB | Output is correct |

49 | Correct | 43 ms | 4088 KB | Output is correct |

50 | Correct | 43 ms | 4088 KB | Output is correct |

51 | Correct | 363 ms | 6396 KB | Output is correct |

52 | Correct | 10 ms | 2296 KB | Output is correct |

53 | Correct | 750 ms | 7280 KB | Output is correct |

54 | Correct | 754 ms | 7152 KB | Output is correct |

55 | Correct | 12 ms | 2296 KB | Output is correct |

56 | Correct | 9 ms | 2296 KB | Output is correct |

57 | Correct | 18 ms | 1656 KB | Output is correct |

58 | Correct | 740 ms | 7284 KB | Output is correct |

59 | Correct | 18 ms | 2680 KB | Output is correct |

60 | Correct | 10 ms | 2296 KB | Output is correct |

61 | Correct | 19 ms | 2808 KB | Output is correct |

62 | Correct | 18 ms | 2808 KB | Output is correct |

63 | Correct | 92 ms | 3832 KB | Output is correct |

64 | Correct | 62 ms | 3672 KB | Output is correct |

65 | Correct | 17 ms | 2680 KB | Output is correct |

66 | Correct | 19 ms | 2700 KB | Output is correct |

67 | Correct | 82 ms | 4572 KB | Output is correct |

68 | Correct | 55 ms | 3704 KB | Output is correct |

69 | Correct | 18 ms | 2808 KB | Output is correct |

70 | Correct | 39 ms | 3832 KB | Output is correct |

71 | Correct | 79 ms | 4504 KB | Output is correct |

72 | Correct | 63 ms | 4472 KB | Output is correct |

73 | Correct | 11 ms | 2296 KB | Output is correct |

74 | Correct | 38 ms | 3832 KB | Output is correct |

75 | Correct | 65 ms | 4472 KB | Output is correct |

76 | Correct | 28 ms | 3192 KB | Output is correct |

77 | Correct | 151 ms | 5212 KB | Output is correct |

78 | Correct | 29 ms | 2296 KB | Output is correct |

79 | Correct | 68 ms | 3320 KB | Output is correct |

80 | Correct | 27 ms | 3320 KB | Output is correct |

81 | Correct | 142 ms | 5136 KB | Output is correct |

82 | Correct | 6 ms | 1784 KB | Output is correct |

83 | Correct | 130 ms | 3324 KB | Output is correct |

84 | Correct | 66 ms | 4472 KB | Output is correct |

85 | Correct | 6 ms | 1784 KB | Output is correct |

86 | Correct | 66 ms | 4344 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 3 ms | 1528 KB | Output is correct |

2 | Correct | 3 ms | 1528 KB | Output is correct |

3 | Correct | 11 ms | 2168 KB | Output is correct |

4 | Correct | 9 ms | 2168 KB | Output is correct |

5 | Correct | 9 ms | 2168 KB | Output is correct |

6 | Correct | 10 ms | 2168 KB | Output is correct |

7 | Correct | 10 ms | 2168 KB | Output is correct |

8 | Correct | 4 ms | 1656 KB | Output is correct |

9 | Correct | 3 ms | 1528 KB | Output is correct |

10 | Correct | 4 ms | 1660 KB | Output is correct |

11 | Correct | 10 ms | 2296 KB | Output is correct |

12 | Correct | 9 ms | 2296 KB | Output is correct |

13 | Correct | 3 ms | 1528 KB | Output is correct |

14 | Correct | 10 ms | 2296 KB | Output is correct |

15 | Correct | 3 ms | 1528 KB | Output is correct |

16 | Correct | 10 ms | 2296 KB | Output is correct |

17 | Correct | 4 ms | 1528 KB | Output is correct |

18 | Correct | 12 ms | 2296 KB | Output is correct |

19 | Correct | 4 ms | 1656 KB | Output is correct |

20 | Correct | 7 ms | 2056 KB | Output is correct |

21 | Correct | 7 ms | 2040 KB | Output is correct |

22 | Correct | 4 ms | 1656 KB | Output is correct |

23 | Correct | 13 ms | 2296 KB | Output is correct |

24 | Correct | 5 ms | 1656 KB | Output is correct |

25 | Correct | 13 ms | 2296 KB | Output is correct |

26 | Correct | 12 ms | 2296 KB | Output is correct |

27 | Correct | 10 ms | 2168 KB | Output is correct |

28 | Correct | 12 ms | 2296 KB | Output is correct |

29 | Correct | 11 ms | 2168 KB | Output is correct |

30 | Correct | 13 ms | 2424 KB | Output is correct |

31 | Correct | 14 ms | 2428 KB | Output is correct |

32 | Correct | 14 ms | 2424 KB | Output is correct |

33 | Correct | 13 ms | 2424 KB | Output is correct |

34 | Correct | 14 ms | 2428 KB | Output is correct |

35 | Correct | 9 ms | 1912 KB | Output is correct |

36 | Correct | 8 ms | 1912 KB | Output is correct |

37 | Correct | 8 ms | 1888 KB | Output is correct |

38 | Correct | 6 ms | 1756 KB | Output is correct |

39 | Correct | 6 ms | 1788 KB | Output is correct |

40 | Correct | 19 ms | 2820 KB | Output is correct |

41 | Correct | 6 ms | 1784 KB | Output is correct |

42 | Correct | 19 ms | 2808 KB | Output is correct |

43 | Correct | 20 ms | 2936 KB | Output is correct |

44 | Correct | 3 ms | 1528 KB | Output is correct |

45 | Correct | 398 ms | 20432 KB | Output is correct |

46 | Correct | 176 ms | 12108 KB | Output is correct |

47 | Correct | 438 ms | 21688 KB | Output is correct |

48 | Correct | 391 ms | 21636 KB | Output is correct |

49 | Correct | 95 ms | 9324 KB | Output is correct |

50 | Correct | 467 ms | 27288 KB | Output is correct |

51 | Correct | 387 ms | 21596 KB | Output is correct |

52 | Correct | 91 ms | 9204 KB | Output is correct |

53 | Correct | 99 ms | 9300 KB | Output is correct |

54 | Correct | 15 ms | 2296 KB | Output is correct |

55 | Correct | 591 ms | 27500 KB | Output is correct |

56 | Correct | 66 ms | 6380 KB | Output is correct |

57 | Correct | 94 ms | 9328 KB | Output is correct |

58 | Correct | 153 ms | 11712 KB | Output is correct |

59 | Correct | 66 ms | 6384 KB | Output is correct |

60 | Correct | 62 ms | 6384 KB | Output is correct |

61 | Correct | 155 ms | 11768 KB | Output is correct |

62 | Correct | 122 ms | 9120 KB | Output is correct |

63 | Correct | 206 ms | 13812 KB | Output is correct |

64 | Correct | 62 ms | 6512 KB | Output is correct |

65 | Correct | 271 ms | 16496 KB | Output is correct |

66 | Correct | 191 ms | 9200 KB | Output is correct |

67 | Correct | 205 ms | 13736 KB | Output is correct |

68 | Correct | 247 ms | 15700 KB | Output is correct |

69 | Correct | 266 ms | 16368 KB | Output is correct |

70 | Correct | 120 ms | 9072 KB | Output is correct |

71 | Correct | 252 ms | 15728 KB | Output is correct |

72 | Correct | 226 ms | 13296 KB | Output is correct |

73 | Correct | 328 ms | 18088 KB | Output is correct |

74 | Correct | 125 ms | 9072 KB | Output is correct |

75 | Correct | 103 ms | 8084 KB | Output is correct |

76 | Correct | 205 ms | 13296 KB | Output is correct |

77 | Correct | 313 ms | 18140 KB | Output is correct |

78 | Correct | 149 ms | 9964 KB | Output is correct |

79 | Correct | 104 ms | 8052 KB | Output is correct |

80 | Correct | 47 ms | 4984 KB | Output is correct |

81 | Correct | 141 ms | 9844 KB | Output is correct |

82 | Correct | 230 ms | 15016 KB | Output is correct |

83 | Correct | 47 ms | 4856 KB | Output is correct |

84 | Correct | 232 ms | 15120 KB | Output is correct |