Submission #1179476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179476		Alish	Political Development (BOI17_politicaldevelopment)	C++20	77 / 100	3094 ms	6028 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;

const int N = 5e4+23, K=13;

vector<int> g[N];

int G[N], dp[1<<K];
int ind[N], deg[N];
int n, k;

int f(vector<int> vec){
    sort(all(vec));
    int n=vec.size();
    for (int i=0; i<n; i++){
        G[i]=0;
        for (int u: g[vec[i]]){
            int t=lower_bound(all(vec), u)-vec.begin();
            if(t<vec.size() && vec[t]==u)G[i]|=(1<<t);
        }
    }
    for (int mask=1; mask<(1<<n); mask++){
        int k=__builtin_ctz(mask);
        dp[mask]=max(dp[mask^(1<<k)], dp[mask&G[k]]+1);
    }
    return dp[(1<<n)-1];
}

int main()
{
    fast_io
    cin>>n>>k;
    queue<int> q;
    for (int i=0; i<n; i++){
        cin>>deg[i];
        for (int j=0; j<deg[i]; j++){
            int u; cin>>u;
            g[i].pb(u);
        }
        if(deg[i]<k) q.push(i);
    }

    int num=0;
    while(!q.empty()){
        int v=q.front();
        q.pop();
        ind[v]=num++;
        for (int u: g[v]){
            deg[u]--;
            if(deg[u]==k-1) q.push(u);
        }
    }
    int ans=1;
    for (int v=0; v<n; v++){
        vector<int> vec; vec.pb(v);
        for (int u: g[v]) if(ind[v]<ind[u]) vec.pb(u);
        ans=max(ans, f(vec));
    }
    cout<<ans<<endl;
}

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