답안 #311102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
311102	2020-10-09T09:11:52 Z	Vladth11	Political Development (BOI17_politicaldevelopment)	C++14	4 / 100	3000 ms	6632 KB

politicaldevelopment

#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;

vector <int> v[NMAX];
unordered_set <int> st;

int main() {
    // ifstream cin("catsfood.in");
    // ofstream cout("catsfood.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k, i, d;
    cin >> n >> k;
    for(i = 1; i <= n; i++) {
        int d;
        cin >> d;
        v[i].push_back(i);
        while(d--) {
            int x;
            cin >> x;
            v[i].push_back(x + 1);
        }
        sort(v[i].begin(), v[i].end());
    }
    int maxim = 0;
    for(i = 1; i <= n; i++) {
        int nrbits = v[i].size();
       // debug(i);
      if(nrbits > k)
        continue;
        for(int mask = 1; mask < (1 << nrbits); mask++) {
            st.clear();
            int cnt = 0;
            for(int j = nrbits - 1; j >= 0; j--) {
                if(mask & (1 << j)) {
                    for(auto x : v[v[i][j]]) {
                        if(st.find(x) != st.end())
                            cnt++;
                    }
                    st.insert(v[i][j]);
                }
            }
            int bb = __builtin_popcount(mask);
         //   debug_with_space(mask);
           // debug(cnt);
            if(cnt == bb * (bb - 1) / 2)
                maxim = max(maxim, bb);
        }
    }
    cout << maxim;
    return 0;
}

Compilation message

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:41:7: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   41 |       if(nrbits > k)
      |       ^~
politicaldevelopment.cpp:43:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   43 |         for(int mask = 1; mask < (1 << nrbits); mask++) {
      |         ^~~
politicaldevelopment.cpp:24:18: warning: unused variable 'd' [-Wunused-variable]
   24 |     int n, k, i, d;
      |                  ^

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	5 ms	2816 KB	Output is correct
4	Correct	354 ms	2936 KB	Output is correct
5	Correct	350 ms	2816 KB	Output is correct
6	Correct	11 ms	2848 KB	Output is correct
7	Correct	11 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	2 ms	2688 KB	Output is correct
10	Correct	3 ms	2816 KB	Output is correct

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	5 ms	2816 KB	Output is correct
4	Correct	354 ms	2936 KB	Output is correct
5	Correct	350 ms	2816 KB	Output is correct
6	Correct	11 ms	2848 KB	Output is correct
7	Correct	11 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	2 ms	2688 KB	Output is correct
10	Correct	3 ms	2816 KB	Output is correct
11	Correct	351 ms	2816 KB	Output is correct
12	Correct	355 ms	2936 KB	Output is correct
13	Correct	2 ms	2688 KB	Output is correct
14	Correct	351 ms	2916 KB	Output is correct
15	Correct	2 ms	2688 KB	Output is correct
16	Correct	11 ms	2816 KB	Output is correct
17	Correct	2 ms	2688 KB	Output is correct
18	Correct	12 ms	2816 KB	Output is correct
19	Correct	4 ms	2816 KB	Output is correct
20	Correct	5 ms	2816 KB	Output is correct
21	Correct	5 ms	2816 KB	Output is correct
22	Correct	3 ms	2816 KB	Output is correct
23	Incorrect	7 ms	2816 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #3
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2816 KB	Output is correct
2	Correct	3 ms	2688 KB	Output is correct
3	Correct	2 ms	2688 KB	Output is correct
4	Correct	2 ms	2688 KB	Output is correct
5	Correct	2 ms	2688 KB	Output is correct
6	Correct	2 ms	2688 KB	Output is correct
7	Correct	2 ms	2688 KB	Output is correct
8	Correct	2 ms	2688 KB	Output is correct
9	Correct	2 ms	2688 KB	Output is correct
10	Correct	2 ms	2688 KB	Output is correct
11	Execution timed out	3068 ms	6632 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4
0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	5 ms	2816 KB	Output is correct
4	Correct	354 ms	2936 KB	Output is correct
5	Correct	350 ms	2816 KB	Output is correct
6	Correct	11 ms	2848 KB	Output is correct
7	Correct	11 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	2 ms	2688 KB	Output is correct
10	Correct	3 ms	2816 KB	Output is correct
11	Correct	351 ms	2816 KB	Output is correct
12	Correct	355 ms	2936 KB	Output is correct
13	Correct	2 ms	2688 KB	Output is correct
14	Correct	351 ms	2916 KB	Output is correct
15	Correct	2 ms	2688 KB	Output is correct
16	Correct	11 ms	2816 KB	Output is correct
17	Correct	2 ms	2688 KB	Output is correct
18	Correct	12 ms	2816 KB	Output is correct
19	Correct	4 ms	2816 KB	Output is correct
20	Correct	5 ms	2816 KB	Output is correct
21	Correct	5 ms	2816 KB	Output is correct
22	Correct	3 ms	2816 KB	Output is correct
23	Incorrect	7 ms	2816 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2688 KB	Output is correct
2	Correct	2 ms	2688 KB	Output is correct
3	Correct	5 ms	2816 KB	Output is correct
4	Correct	354 ms	2936 KB	Output is correct
5	Correct	350 ms	2816 KB	Output is correct
6	Correct	11 ms	2848 KB	Output is correct
7	Correct	11 ms	2816 KB	Output is correct
8	Correct	3 ms	2816 KB	Output is correct
9	Correct	2 ms	2688 KB	Output is correct
10	Correct	3 ms	2816 KB	Output is correct
11	Correct	351 ms	2816 KB	Output is correct
12	Correct	355 ms	2936 KB	Output is correct
13	Correct	2 ms	2688 KB	Output is correct
14	Correct	351 ms	2916 KB	Output is correct
15	Correct	2 ms	2688 KB	Output is correct
16	Correct	11 ms	2816 KB	Output is correct
17	Correct	2 ms	2688 KB	Output is correct
18	Correct	12 ms	2816 KB	Output is correct
19	Correct	4 ms	2816 KB	Output is correct
20	Correct	5 ms	2816 KB	Output is correct
21	Correct	5 ms	2816 KB	Output is correct
22	Correct	3 ms	2816 KB	Output is correct
23	Incorrect	7 ms	2816 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

답안 #311102

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 0 / 12.0

Subtask #3 0 / 23.0

Subtask #4 0 / 38.0

Subtask #5 0 / 23.0

Subtask #1
4.0 / 4.0

Subtask #2
0 / 12.0

Subtask #3
0 / 23.0

Subtask #4
0 / 38.0

Subtask #5
0 / 23.0