Submission #1306186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306186		zxzuam	Political Development (BOI17_politicaldevelopment)	C++20	39 / 100	3094 ms	24108 KiB

politicaldevelopment

#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;
set <int> vv;
void dfs(int v) {
    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.erase(vv.find(v));
}
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);
        }
    }
    for(int i = 1; i <= n; i++) {
        dfs( i);
    }
    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();
    }
}

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