Submission #134254

#	Time	Username	Problem	Language	Result	Execution time	Memory
134254		Kastanda	Political Development (BOI17_politicaldevelopment)	C++11	100 / 100	536 ms	28964 KiB

politicaldevelopment

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 50005, K = 10;
int n, k, Mx, M[K], dp[1 << K];
set < int > Adj[N];
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		int d, v;
		scanf("%d", &d);
		for (int j = 0; j < d; j++)
			scanf("%d", &v), Adj[i].insert(v);
	}
	set < pair < int , int > > A;
	for (int i = 0; i < n; i++)
		A.insert({(int)Adj[i].size(), i});
	while (1)
	{
		if (A.size() <= 1)
		{
			Mx = max(Mx, (int)A.size());
			break;
		}
		int v = A.begin()->second;
		A.erase(A.begin());
		vector < int > vec;
		for (int u : Adj[v])
		{
			vec.pb(u);
			A.erase({(int)Adj[u].size(), u});
			Adj[u].erase(v);
			A.insert({(int)Adj[u].size(), u});
		}
		Adj[v].clear();
		int d = (int)vec.size();
		for (int i = 0; i < d; i++)
		{
			M[i] = (1 << i);
			for (int j = 0; j < d; j++)
				if (Adj[vec[i]].count(vec[j]))
					M[i] |= (1 << j);
		}
		dp[0] = 1;
		for (int i = 1; i < (1 << d); i++)
		{
			int lb = __builtin_ctz(i); dp[i] = 0;
			if (dp[i ^ (1 << lb)] && ((M[lb] & i) == i))
				dp[i] = 1, Mx = max(Mx, __builtin_popcount(i) + 1);
		}
 
	}
 
	return !printf("%d\n", Mx);
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d);
   ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:15:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &v), Adj[i].insert(v);
    ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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