Submission #994460

#	Time	Username	Problem	Language	Result	Execution time	Memory
994460		amine_aroua	Political Development (BOI17_politicaldevelopment)	C++17	16 / 100	237 ms	306520 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;
bitset<N> vis = 0;
int maxClique(int i)
{
    vis = 0;
    vis[i] = 1;
    cur = adj[i];
    int last = i;
    int cnt = 0;
    while(cnt < k)
    {
        cnt++;
        cur&=adj[last];
        if(cur == 0)
            break;
        int before = last;
        for(int j = cur._Find_first() ; j < N ; j = cur._Find_next(i))
        {
            if(done[j] || vis[j])
                continue;
            last = j;
            break;
        }
        if(before == last)
            break;
        vis[last] = 1;
    }
    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;
            adj[i][x] = 1;
        }
    }
    int best = 0;
    fore(i , n)
    {
        best = max(best , maxClique(i));
        done[i] = 1;
    }
    cout<<best<<nl;
}

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