Submission #439531

#TimeUsernameProblemLanguageResultExecution timeMemory
439531K4YANPolitical Development (BOI17_politicaldevelopment)C++17
16 / 100
3096 ms40340 KiB
//Be Name Khoda
// 10:55 -> 10:50 shoroo
// 12:05 | 12:05

#include<bits/stdc++.h>

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 short int mxn = 5e3 + 1;
int n, k, q, w;
short int v;
vector<int> dp[mxn][11];
vector<short int> kmk;
vector<vector<short int>> g[11];
bool edge[mxn][mxn];

void input() {

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

}

void solve() {

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

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

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

                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(short 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
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...