Submission #994472

#	Time	Username	Problem	Language	Result	Execution time	Memory
994472		amine_aroua	Political Development (BOI17_politicaldevelopment)	C++17	4 / 100	115 ms	306608 KiB

politicaldevelopment

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define int long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
const int N = 50000;
vector<bitset<N>> adj(N , 0);
bool done[N];
int n , k;
bitset<N> cur = 0;
int maxClique(int i)
{
    cur = adj[i];
    int last = i;
    int cnt = 0;
    while(true)
    {
        cnt++;
        cur&=adj[last];
        int before = last;
        for(int j = cur._Find_first() ; j < N ; j = cur._Find_next(j))
        {
            if(done[j])
                continue;
            last = j;
            break;
        }
        if(before == last)
            break;
    }
    return cnt;
}
signed main() {
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
    cin>>n>>k;

    fore(i , n)
    {
        int d;
        cin>>d;
        fore(j , d)
        {
            int x;
            cin>>x;
            if(x != i)
                adj[i][x] = 1;
        }
    }
    int best = 0;
    vector<int> p(n);
    fore(i , n)
        p[i] = i;
    random_shuffle(p.begin() , p.end());
    fore(i , n)
    {
        best = max(best , maxClique(p[i]));
        done[p[i]] = 1;
    }
    cout<<best<<nl;
}

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