Submission #1116012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116012		vjudge1	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	169 ms	21236 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;

#define isz(a) (int)(a).size()

const int NM = 5e4, KM = 10, BL = 320;

int N, K;
vector <int> adj[NM+5];
vector <vector <int> > clique[KM+5];

vector <int> common(vector <int> &a, vector <int> &b){
    vector <int> c = {};
    if (isz(a) > isz(b)){
        for (int i = 0; i < isz(b); i++){
            if (b[i] > a.back()) break;
            int j = lower_bound(a.begin(), a.end(), b[i])-a.begin();
            if (b[i] == a[j]) c.push_back(b[i]);
        }
    }
    else{
        for (int i = 0; i < isz(a); i++){
            if (a[i] > b.back()) break;
            int j = lower_bound(b.begin(), b.end(), a[i])-b.begin();
            if (a[i] == b[j]) c.push_back(a[i]);
        }
    }
    return c;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++){
        int k; cin >> k;
        adj[i].resize(k);
        for (int &j : adj[i]) cin >> j;
        sort(adj[i].begin(), adj[i].end());
    }
    for (int i = 0; i < N; i++) clique[1].push_back({i});
    for (int i = 1; i < K; i++){
        vector <int> vlist, arr_next;
        for (vector <int> arr : clique[i]){
            int mn = 0;
            for (int j = 1; j < i; j++)
                if (isz(adj[arr[j]]) < isz(adj[arr[mn]])) mn = j;
            vlist = adj[arr[mn]];
            for (int j = 0; j < i; j++)
                if (j != mn) vlist = common(vlist, adj[arr[j]]);
            for (int x : vlist){
                if (x <= arr.back()) continue;
                arr_next = arr;
                arr_next.push_back(x);
                clique[i+1].push_back(arr_next);
            }
        }
    }
    int res = K;
    while (isz(clique[res]) == 0) res--;
    cout << res;
    return 0;
}

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