Submission #1306182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306182		zxzuam	Political Development (BOI17_politicaldevelopment)	C++20	39 / 100	3096 ms	24512 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;
mt19937 rng( chrono::steady_clock::now().time_since_epoch().count() );
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);
    bool sub3 = 1;
    vector <pair <int,int>> vvv;
    for(int i = 1; i <= n; i++ ){
        cin >> d[i];
        vvv.emplace_back( d[i], i );
        if(d[i] > 10) {
            sub3 = 0;
        }
        for(int j = 0; j < d[i]; j++) {
            int x;
            cin >> x;
            x++;
            g[ i ].insert(x);
        }
    }
    if(sub3 == 1 || (k <= 3 && n <= 5000)) {
    for(int i = 1; i <= n; i++) {
        dfs(i, {});
    }
    cout << ans;
    return;
    }
    else{
        for(int i = 1; i <= min(300, n); i++) {
            dfs(i, {});
        }
        for(int i = n; i >= max(1, n - 300); i--) {
            dfs(i, {});
        }
        sort(vvv.begin(), vvv.end());
        reverse(vvv.begin(), vvv.end());
        for(int j = 0; j < min(301, (int)vvv.size()); j++ ){
            int i = vvv[j].second;
            dfs(i, {});
        }
        for(int j = 0; j < 300; j++) {
            int i = rng() % n + 1;
            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