# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
311254 | 2020-10-09T19:25:58 Z | Vladth11 | Political Development (BOI17_politicaldevelopment) | C++14 | 3000 ms | 31608 KB |
#include <bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debug_with_space(x) cerr << #x << " " << x << " " using namespace std; typedef long long ll; typedef pair <ll, ll> pii; typedef pair <ll, pii> muchie; const ll NMAX = 100005; const ll INF = (1LL << 60); const ll MOD = 1000000007; const ll BLOCK = 101; set <int> v[NMAX],st; int maxim = 0,k; int deg[NMAX]; set <pii> pq; void afiseaza(int x){ for(auto i : v[x]) debug_with_space(i); cerr << "\n"; } void clique(int i) { int nrbits = v[i].size(); // debug(i); for(int mask = 1; mask < (1 << nrbits); mask++) { int cnt = 0;int bb = __builtin_popcount(mask); if(bb > k || bb < maxim) continue; int j = 0,cc = 0; st.clear(); for(auto y : v[i]){ if(mask & (1 << j)) st.insert(y); j++; } j = 0; for(auto y : v[i]) { if(mask & (1 << j)) { // debug(y); for(auto x : v[y]) { // debug(x); if(st.find(x) != st.end()) cnt++; } } j++; } // debug_with_space(mask); //debug(cnt); if(cnt == bb * bb) maxim = max(maxim, bb); } //debug(maxim); for(auto x : v[i]){ //if(pq.size()) if(x == i) continue; pq.erase({v[x].size(),x}); v[x].erase(i); pq.insert({v[x].size(),x}); } //debug(maxim); } struct cmp{ bool operator()(int x, int y){ return v[x].size() < v[y].size(); } }; int main() { // ifstream cin("catsfood.in"); // ofstream cout("catsfood.out"); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, i, d; cin >> n >> k; for(i = 1; i <= n; i++) { int d; cin >> d; v[i].insert(i); while(d--) { int x; cin >> x; v[i].insert(x + 1); v[x + 1].insert(i); } } for(i = 1; i <= n; i++) { pq.insert({v[i].size(),i}); } while(!pq.empty()){ int top = (*pq.begin()).second; pq.erase(pq.begin()); clique(top); } cout << maxim; return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 3 ms | 4992 KB | Output is correct |
3 | Correct | 11 ms | 6016 KB | Output is correct |
4 | Correct | 211 ms | 6016 KB | Output is correct |
5 | Correct | 206 ms | 6016 KB | Output is correct |
6 | Correct | 14 ms | 6016 KB | Output is correct |
7 | Correct | 14 ms | 6016 KB | Output is correct |
8 | Correct | 6 ms | 5632 KB | Output is correct |
9 | Correct | 3 ms | 4992 KB | Output is correct |
10 | Correct | 6 ms | 5632 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 3 ms | 4992 KB | Output is correct |
3 | Correct | 11 ms | 6016 KB | Output is correct |
4 | Correct | 211 ms | 6016 KB | Output is correct |
5 | Correct | 206 ms | 6016 KB | Output is correct |
6 | Correct | 14 ms | 6016 KB | Output is correct |
7 | Correct | 14 ms | 6016 KB | Output is correct |
8 | Correct | 6 ms | 5632 KB | Output is correct |
9 | Correct | 3 ms | 4992 KB | Output is correct |
10 | Correct | 6 ms | 5632 KB | Output is correct |
11 | Correct | 214 ms | 6100 KB | Output is correct |
12 | Correct | 221 ms | 6104 KB | Output is correct |
13 | Correct | 4 ms | 4992 KB | Output is correct |
14 | Correct | 184 ms | 6016 KB | Output is correct |
15 | Correct | 4 ms | 4992 KB | Output is correct |
16 | Correct | 15 ms | 6016 KB | Output is correct |
17 | Correct | 4 ms | 4992 KB | Output is correct |
18 | Correct | 14 ms | 6016 KB | Output is correct |
19 | Correct | 6 ms | 5632 KB | Output is correct |
20 | Correct | 8 ms | 5760 KB | Output is correct |
21 | Correct | 8 ms | 5760 KB | Output is correct |
22 | Correct | 6 ms | 5632 KB | Output is correct |
23 | Correct | 12 ms | 6144 KB | Output is correct |
24 | Correct | 6 ms | 5632 KB | Output is correct |
25 | Correct | 14 ms | 6144 KB | Output is correct |
26 | Correct | 13 ms | 6144 KB | Output is correct |
27 | Correct | 11 ms | 6016 KB | Output is correct |
28 | Correct | 13 ms | 6144 KB | Output is correct |
29 | Correct | 11 ms | 6016 KB | Output is correct |
30 | Correct | 70 ms | 6144 KB | Output is correct |
31 | Correct | 14 ms | 6144 KB | Output is correct |
32 | Correct | 72 ms | 6264 KB | Output is correct |
33 | Correct | 14 ms | 6144 KB | Output is correct |
34 | Correct | 14 ms | 6144 KB | Output is correct |
35 | Correct | 9 ms | 5632 KB | Output is correct |
36 | Correct | 9 ms | 5632 KB | Output is correct |
37 | Correct | 9 ms | 5632 KB | Output is correct |
38 | Correct | 9 ms | 5376 KB | Output is correct |
39 | Correct | 9 ms | 5376 KB | Output is correct |
40 | Correct | 18 ms | 6528 KB | Output is correct |
41 | Correct | 9 ms | 5376 KB | Output is correct |
42 | Correct | 18 ms | 6528 KB | Output is correct |
43 | Correct | 20 ms | 6528 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5632 KB | Output is correct |
2 | Correct | 4 ms | 4992 KB | Output is correct |
3 | Correct | 4 ms | 4992 KB | Output is correct |
4 | Correct | 3 ms | 4992 KB | Output is correct |
5 | Correct | 4 ms | 4992 KB | Output is correct |
6 | Correct | 4 ms | 4992 KB | Output is correct |
7 | Correct | 3 ms | 4992 KB | Output is correct |
8 | Correct | 4 ms | 4992 KB | Output is correct |
9 | Correct | 3 ms | 4992 KB | Output is correct |
10 | Correct | 4 ms | 4992 KB | Output is correct |
11 | Execution timed out | 3086 ms | 31608 KB | Time limit exceeded |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 3 ms | 4992 KB | Output is correct |
3 | Correct | 11 ms | 6016 KB | Output is correct |
4 | Correct | 211 ms | 6016 KB | Output is correct |
5 | Correct | 206 ms | 6016 KB | Output is correct |
6 | Correct | 14 ms | 6016 KB | Output is correct |
7 | Correct | 14 ms | 6016 KB | Output is correct |
8 | Correct | 6 ms | 5632 KB | Output is correct |
9 | Correct | 3 ms | 4992 KB | Output is correct |
10 | Correct | 6 ms | 5632 KB | Output is correct |
11 | Correct | 214 ms | 6100 KB | Output is correct |
12 | Correct | 221 ms | 6104 KB | Output is correct |
13 | Correct | 4 ms | 4992 KB | Output is correct |
14 | Correct | 184 ms | 6016 KB | Output is correct |
15 | Correct | 4 ms | 4992 KB | Output is correct |
16 | Correct | 15 ms | 6016 KB | Output is correct |
17 | Correct | 4 ms | 4992 KB | Output is correct |
18 | Correct | 14 ms | 6016 KB | Output is correct |
19 | Correct | 6 ms | 5632 KB | Output is correct |
20 | Correct | 8 ms | 5760 KB | Output is correct |
21 | Correct | 8 ms | 5760 KB | Output is correct |
22 | Correct | 6 ms | 5632 KB | Output is correct |
23 | Correct | 12 ms | 6144 KB | Output is correct |
24 | Correct | 6 ms | 5632 KB | Output is correct |
25 | Correct | 14 ms | 6144 KB | Output is correct |
26 | Correct | 13 ms | 6144 KB | Output is correct |
27 | Correct | 11 ms | 6016 KB | Output is correct |
28 | Correct | 13 ms | 6144 KB | Output is correct |
29 | Correct | 11 ms | 6016 KB | Output is correct |
30 | Correct | 70 ms | 6144 KB | Output is correct |
31 | Correct | 14 ms | 6144 KB | Output is correct |
32 | Correct | 72 ms | 6264 KB | Output is correct |
33 | Correct | 14 ms | 6144 KB | Output is correct |
34 | Correct | 14 ms | 6144 KB | Output is correct |
35 | Correct | 9 ms | 5632 KB | Output is correct |
36 | Correct | 9 ms | 5632 KB | Output is correct |
37 | Correct | 9 ms | 5632 KB | Output is correct |
38 | Correct | 9 ms | 5376 KB | Output is correct |
39 | Correct | 9 ms | 5376 KB | Output is correct |
40 | Correct | 18 ms | 6528 KB | Output is correct |
41 | Correct | 9 ms | 5376 KB | Output is correct |
42 | Correct | 18 ms | 6528 KB | Output is correct |
43 | Correct | 20 ms | 6528 KB | Output is correct |
44 | Correct | 25 ms | 7424 KB | Output is correct |
45 | Correct | 4 ms | 4992 KB | Output is correct |
46 | Correct | 21 ms | 6528 KB | Output is correct |
47 | Correct | 106 ms | 7544 KB | Output is correct |
48 | Correct | 21 ms | 6656 KB | Output is correct |
49 | Correct | 107 ms | 7544 KB | Output is correct |
50 | Correct | 125 ms | 7552 KB | Output is correct |
51 | Execution timed out | 3072 ms | 9336 KB | Time limit exceeded |
52 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 3 ms | 4992 KB | Output is correct |
3 | Correct | 11 ms | 6016 KB | Output is correct |
4 | Correct | 211 ms | 6016 KB | Output is correct |
5 | Correct | 206 ms | 6016 KB | Output is correct |
6 | Correct | 14 ms | 6016 KB | Output is correct |
7 | Correct | 14 ms | 6016 KB | Output is correct |
8 | Correct | 6 ms | 5632 KB | Output is correct |
9 | Correct | 3 ms | 4992 KB | Output is correct |
10 | Correct | 6 ms | 5632 KB | Output is correct |
11 | Correct | 214 ms | 6100 KB | Output is correct |
12 | Correct | 221 ms | 6104 KB | Output is correct |
13 | Correct | 4 ms | 4992 KB | Output is correct |
14 | Correct | 184 ms | 6016 KB | Output is correct |
15 | Correct | 4 ms | 4992 KB | Output is correct |
16 | Correct | 15 ms | 6016 KB | Output is correct |
17 | Correct | 4 ms | 4992 KB | Output is correct |
18 | Correct | 14 ms | 6016 KB | Output is correct |
19 | Correct | 6 ms | 5632 KB | Output is correct |
20 | Correct | 8 ms | 5760 KB | Output is correct |
21 | Correct | 8 ms | 5760 KB | Output is correct |
22 | Correct | 6 ms | 5632 KB | Output is correct |
23 | Correct | 12 ms | 6144 KB | Output is correct |
24 | Correct | 6 ms | 5632 KB | Output is correct |
25 | Correct | 14 ms | 6144 KB | Output is correct |
26 | Correct | 13 ms | 6144 KB | Output is correct |
27 | Correct | 11 ms | 6016 KB | Output is correct |
28 | Correct | 13 ms | 6144 KB | Output is correct |
29 | Correct | 11 ms | 6016 KB | Output is correct |
30 | Correct | 70 ms | 6144 KB | Output is correct |
31 | Correct | 14 ms | 6144 KB | Output is correct |
32 | Correct | 72 ms | 6264 KB | Output is correct |
33 | Correct | 14 ms | 6144 KB | Output is correct |
34 | Correct | 14 ms | 6144 KB | Output is correct |
35 | Correct | 9 ms | 5632 KB | Output is correct |
36 | Correct | 9 ms | 5632 KB | Output is correct |
37 | Correct | 9 ms | 5632 KB | Output is correct |
38 | Correct | 9 ms | 5376 KB | Output is correct |
39 | Correct | 9 ms | 5376 KB | Output is correct |
40 | Correct | 18 ms | 6528 KB | Output is correct |
41 | Correct | 9 ms | 5376 KB | Output is correct |
42 | Correct | 18 ms | 6528 KB | Output is correct |
43 | Correct | 20 ms | 6528 KB | Output is correct |
44 | Correct | 3 ms | 4992 KB | Output is correct |
45 | Correct | 588 ms | 24548 KB | Output is correct |
46 | Execution timed out | 3077 ms | 17656 KB | Time limit exceeded |
47 | Halted | 0 ms | 0 KB | - |