Submission #1309025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309025		pasta	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	2441 ms	82360 KiB

politicaldevelopment

//Oh? You're Approaching Me?

#include <bits/stdc++.h>
using namespace std;

//#define int long long

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


// #pragma GCC optimize("O3,unroll-loops")
#define migmig     			ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;

const int maxn = 2e5 + 21;
const int mod = 998244353;
//const int inf = 1e18;
const int LOG = 23;
const int sq = 300;
//g++ main.cpp -o main && main.exe
//#define lc  (id * 2)
//#define rc  (lc + 1)
//#define mid ((l + r) / 2)

bool dp[maxn][1<<10];
unordered_set<int> adj[maxn];

signed main() {
	int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int x;
            cin >> x;
            adj[i].insert(x);
        }
    }
    
    vector<int> ord(n);
    iota(all(ord), 0);
    sort(all(ord), [](int l, int r) {
        return adj[l].size() < adj[r].size();
    });
    
    int ans = 1;
    for (int i : ord) {
    	vector<int> cur;
    	for (auto v : adj[i]) {
    		cur.pb(v);
		}
		dp[i][0] = true;
		for (int mask = 1; mask < (1 << SZ(cur)); mask++) {
			int p = __lg(mask);
			bool ok = dp[i][mask ^ (1 << p)];
			
			for (int j = 0; j < p; j++) {
				if (!(mask & (1 << j)))
					continue;
				ok &= adj[cur[j]].count(cur[p]);
			}
			dp[i][mask] = ok;
			if (ok) {
				ans = max(ans, __builtin_popcount(mask) + 1);
			}
		}
		for (auto v: cur) adj[v].erase(i);
	}
	cout << ans << '\n';
}

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