제출 #1306666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306666		tnt	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	298 ms	9784 KiB

politicaldevelopment

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <set>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    if (!(cin >> N >> K)) return 0;

    vector<vector<int>> adj(N);
    vector<int> degree(N);
    for (int i = 0; i < N; ++i) {
        int d;
        cin >> d;
        degree[i] = d;
        for (int j = 0; j < d; ++j) {
            int neighbor;
            cin >> neighbor;
            adj[i].push_back(neighbor);
        }
    }

    // 1. Находим порядок вырожденности
    vector<int> order;
    vector<int> current_degree = degree;
    vector<bool> deleted(N, false);
    
    // Используем set для симуляции очереди с приоритетами по степени
    set<pair<int, int>> pq;
    for (int i = 0; i < N; ++i) {
        pq.insert({current_degree[i], i});
    }

    vector<vector<int>> forward_adj(N);

    while (!pq.empty()) {
        int v = pq.begin()->second;
        pq.erase(pq.begin());
        deleted[v] = true;
        order.push_back(v);

        for (int neighbor : adj[v]) {
            if (!deleted[neighbor]) {
                pq.erase({current_degree[neighbor], neighbor});
                current_degree[neighbor]--;
                pq.insert({current_degree[neighbor], neighbor});
                // Сохраняем только те ребра, которые идут "вперед" по порядку
                forward_adj[v].push_back(neighbor);
            }
        }
    }

    // Для быстрой проверки существования ребра (O(log K))
    for (int i = 0; i < N; ++i) {
        sort(adj[i].begin(), adj[i].end());
    }

    auto has_edge = [&](int u, int v) {
        return binary_search(adj[u].begin(), adj[u].end(), v);
    };

    int max_clique = 1;

    // 2. Перебор клик для каждой вершины
    for (int v : order) {
        const auto& neighbors = forward_adj[v];
        int m = neighbors.size();
        
        // Перебираем все подмножества соседей (их не более 2^(K-1))
        for (int mask = 0; mask < (1 << m); ++mask) {
            vector<int> subset;
            for (int i = 0; i < m; ++i) {
                if ((mask >> i) & 1) {
                    subset.push_back(neighbors[i]);
                }
            }

            if (subset.size() + 1 <= max_clique) continue;

            // Проверяем, образует ли подмножество клику
            bool is_clique = true;
            for (int i = 0; i < subset.size(); ++i) {
                for (int j = i + 1; j < subset.size(); ++j) {
                    if (!has_edge(subset[i], subset[j])) {
                        is_clique = false;
                        break;
                    }
                }
                if (!is_clique) break;
            }

            if (is_clique) {
                max_clique = max(max_clique, (int)subset.size() + 1);
            }
        }
    }

    cout << max_clique << endl;

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23