oj.uz

Submission #676447

# Submission time Handle Problem Language Result Execution time Memory
676447 2022-12-30T23:31:07 Z bogdanvladmihai Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 7 ms 2012 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K; cin >> N >> K;
    vector<set<int>> G(N);
    for (int i = 0; i < N; i++) {
        int nei; cin >> nei;
        for (int j = 0; j < nei; j++) {
            int x; cin >> x;
            G[i].insert(j);
        }
    }

    priority_queue<pair<int, int>> deg;
    for (int u = 0; u < N; u++) {
        deg.push(make_pair(-(int)G[u].size(), u));
    }

    vector<bool> used(N);
    int answer = 1;
    while (!deg.empty()) {
        int u = deg.top().second;
        deg.pop();

        vector<int> toRemove;
        for (const int &x : G[u]) {
            if (used[x]) {
                toRemove.push_back(x);
            }
        }
        for (const int &x : toRemove) {
            G[u].erase(x);
        }

        int maxSize = (int)G[u].size();
        assert(maxSize < K);
        for (int subset = 0; subset < (1 << maxSize); subset++) {
            vector<int> nodes;
            nodes.push_back(u);
            int id = 0;
            for (const int &v : G[u]) {
                if ((subset & (1 << id)) > 0) {
                    nodes.push_back(v);
                }
                id++;
            }

            bool clique = true;
            for (int i = 0; i < (int)nodes.size() - 1; i++) {
                for (int j = i + 1; j < (int)nodes.size(); j++) {
                    int u = nodes[i], v = nodes[j];
                    if (G[u].find(v) == G[u].end() || G[v].find(u) == G[v].end()) {
                        clique = false;
                    }
                }
            }
            if (clique) {
                answer = max(answer, (int)nodes.size());
            }
        }
        
        used[u] = true;
    }
    
    cout << answer << "\n";
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 5 ms 1032 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Runtime error 7 ms 2012 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 5 ms 1032 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Runtime error 7 ms 2012 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 5 ms 1032 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Runtime error 7 ms 2012 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 5 ms 1032 KB Output is correct
5 Correct 5 ms 1108 KB Output is correct
6 Runtime error 7 ms 2012 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -