oj.uz

Submission #676698

# Submission time Handle Problem Language Result Execution time Memory
676698 2022-12-31T18:02:33 Z bogdanvladmihai Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 2 ms 980 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K; cin >> N >> K;
    vector<set<int>> G(N), T(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(x);
            T[x].insert(i);
        }
    }

    set<pair<int, int>> q;
    for (int i = 0; i < N; i++) {
        q.insert(make_pair((int)G[i].size(), i));
    }

    int answer = 1;
    while (!q.empty()) {
        int u = q.begin() -> second;
        q.erase(q.begin());

        int size = (int)G[u].size();
        for (int subset = 1; subset < (1 << size); 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 && clique; i++) {
                for (int j = i + 1; j < (int)nodes.size() && clique; j++) {
                    if (G[i].find(j) == G[i].end() || G[j].find(i) == G[j].end()) {
                        clique = false;
                    }
                }
            }
            if (clique) {
                answer = max(answer, (int)nodes.size());
            }
        }


        for (const int &x : T[u]) {
            if ((int)G[x].size() > 0) {
                q.erase(make_pair((int)G[x].size(), x));
                G[x].erase(u);
                q.insert(make_pair((int)G[x].size(), x));
            }
        }

        G[u].clear();
    }
    
    cout << answer << "\n";
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 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 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -