Submission #439520

#	Time	Username	Problem	Language	Result	Execution time	Memory
439520		K4YAN	Political Development (BOI17_politicaldevelopment)	C++17	16 / 100	3073 ms	40548 KiB

politicaldevelopment

//Be Name Khoda
// 10:55
// 11:35 | 11:35

#include<bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")

using namespace std;

typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define plll pair<pll, ll>
#define piii pair<pii, int>
#define piiii pair<pii, pii>

const int mxn = 5e3 + 5;
int n, k, q, v, w;
vector<int> dp[mxn][11], kmk;
vector<vector<int>> g[11];
bool edge[mxn][mxn];

void input() {

    int tmp = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> q;
        for(int j = 0; j < q; j++) {
            cin >> v;
            edge[v][i] = edge[i][v] = 1;
            if(i < v) {
                dp[i][2].push_back(tmp);
                dp[v][2].push_back(tmp++);
                g[2].push_back({i, v});
            }
        }
    }

}

void solve() {

    for(int i = 3; i <= k; i++) {
        int tmp = 0;

        for(int j = 0; j < n; j++) {

            for(auto u : g[i - 1]) {

                bool b = true;
                for(auto e : u) {

                    if(edge[j][e] == false) {
                        b = false;
                        break;
                    }

                }

                if(b == false) {
                    continue;
                }
                for(auto e : u) {
                    kmk.push_back(e);
                    dp[e][i].push_back(tmp);
                }
                dp[j][i].push_back(tmp++);
                kmk.push_back(j);
                g[i].push_back(kmk);
                kmk.clear();
            }
        }
        if(int(g[i].size()) == 0) {
            break;
        }
    }

    for(int i = 2; i <= k; i++) {
        if(int(g[i].size()) == 0) {
            cout << i - 1 << endl;
            return;
        }
    }
    cout << k << endl;
    return;

}

int main() {

    ios_base::sync_with_stdio(false);

    input(), solve();

    return 0;

}
/*
5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3
*/

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