제출 #994474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
994474		amine_aroua	Political Development (BOI17_politicaldevelopment)	C++17	39 / 100	326 ms	309536 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);
int n , k;
bitset<N> cur = 0;
//bool done[N];
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);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    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;
    shuffle(p.begin() , p.end() , rng);
    fore(i , n)
    {
        best = max(best , maxClique(p[i]));
//        done[p[i]] = 1;
    }
    cout<<best<<nl;
}

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