Submission #997715

#	Time	Username	Problem	Language	Result	Execution time	Memory
997715		MarwenElarbi	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1256 ms	309588 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
const int nax=5e4+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<bitset<nax>> adj(nax);
int n,k;
int dfs(int x){
    int lst=x;
    auto cur=adj[x];
    int cnt=0;
    while(true){
        cnt++;
        cur&=adj[lst];
        vector<int> tab;
        for (int i = cur._Find_first(); (int)tab.size() < 10 && i < n; i=cur._Find_next(i))
        {
            tab.pb(i);
        }
        if(tab.size()==0) break;
        lst=tab[uniform_int_distribution<int>(0,(int)tab.size()-1)(rng)];
    }
    return cnt;
}
int main(){
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    cin>>n>>k;
    bool test=false;
    for (int i = 0; i < n; ++i)
    {
        int s;
        cin>>s;
        for (int j = 0; j < s; ++j)
        {
            int x;
            cin>>x;
            adj[i][x]=1;
        }
    }
    vector<int> per(n);
    for (int i = 0; i < n; ++i)
    {
        per[i]=i;
    }
    int ans=0;
    for (int i = 0; i < n*5; ++i)
    {
        if(i%n==0) shuffle(per.begin(),per.end(),rng);
        ans=max(ans,dfs(per[i%n]));
    }
    cout <<ans<<endl;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:35:10: warning: unused variable 'test' [-Wunused-variable]
   35 |     bool test=false;
      |          ^~~~

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