oj.uz

답안 #246593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246593 2020-07-09T16:55:05 Z santaclaus03 Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 9 ms 1280 KB 
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

int main() {
    int N, K; cin >> N >> K;
    vvi graph(N);
    vi d(N);
    vector<bool> del(N);
    queue<int> q;
    for (int i = 0; i < N; ++i) {
        graph[i].push_back(i);
        cin >> d[i];
        for (int j = 0; j < d[i]; ++j) {
            int x; cin >> x;
            graph[i].push_back(x);
        }
        if (d[i] < K) q.push(i);
    }
    int ans = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vi p;
        for (int v : graph[u]) if (!del[v]) p.push_back(v);
        int s = p.size();
        vi p_idx(s);
        for (int i = 0; i < s; ++i) p_idx[p[i]] = i;
        vector<int> m(s);
        for (int i = 0; i < s; ++i) for (int j : graph[i]) m[i] |= 1 << p_idx[j];
        for (int c = 1; c < 1 << s; ++c) {
            bool valid = true;
            for (int i = 0; i < s; ++i) {
                if (c & (1 << i) && (c & !m[i])) {
                    valid = false;
                    break;
                }
            }
            if (valid) ans = max(ans, __builtin_popcount(c));
        }
        del[u] = true;
        for (int v : graph[u]) if (--d[v] == K - 1) q.push(v);
    }
    cout << ans << endl;
    return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 9 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -