Submission #1306177

#TimeUsernameProblemLanguageResultExecution timeMemory
1306177zxzuamPolitical Development (BOI17_politicaldevelopment)C++20
39 / 100
3094 ms24308 KiB
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
constexpr int MAXN = 50009;
set <int> g[MAXN];
vector <int> d;
int ans = 1;
int n, k;
void dfs(int v, set <int> vv) {
    if(d[v] < (int)vv.size()) return;
    for(auto j : vv) {
        if( !g[ v ].count( j ) ) {return;}
    }
    vv.insert(v);
    if((int)vv.size() == k) {
        cout << k;
        exit(0);
    }
    ans = max(ans, (int)vv.size() );
    for(auto to : g[v]) {
        if( !vv.count( to ) ) {
            dfs(to, vv);
        }
    }
}
void solve() {
    cin >> n >> k;
    d.resize(n + 1);
    for(int i = 1; i <= n; i++ ){
        cin >> d[i];
        for(int j = 0; j < d[i]; j++) {
            int x;
            cin >> x;
            x++;
            g[ i ].insert(x);
        }
    }
    set<int> emp;
    for(int i = 1; i <= n; i++) {
        dfs(i, emp);
    }
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("7-router.in", "r", stdin);
    //freopen("7-router.out.txt", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt--){
        solve();
    }
}
#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...