Submission #235085

#	Time	Username	Problem	Language	Result	Execution time	Memory
235085		luciocf	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	1004 ms	52472 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 5e4+10;

int n, k;

set<int> grafo[maxn], grafo_rev[maxn];

int main(void)
{
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; i++)
	{
		int d;
		scanf("%d", &d);

		for (int j = 0; j < d; j++)
		{
			int v;
			scanf("%d", &v);

			grafo[i].insert(v);
			grafo_rev[v].insert(i);
		}
	}

	set<pii> st;

	for (int i = 0; i < n; i++)
		st.insert({grafo[i].size(), i});

	int ans = 0;

	while (st.size())
	{
		int u = st.begin()->second;
		st.erase(st.begin());

		vector<int> V;
		for (auto v: grafo[u])
			V.push_back(v);

		for (int mask = 0; mask < 1<<((int)V.size()); mask++)
		{
			bool ok = 1;

			for (int i = 0; i < (int)V.size(); i++)
			{
				if (!(mask&(1<<i))) continue;

				for (int j = 0; j < (int)V.size(); j++)
				{
					if (i == j || !(mask&(1<<j))) continue;

					if (grafo[V[i]].find(V[j]) == grafo[V[i]].end())
					{
						ok = 0;
						break;
					}
				}

				if (!ok) break;
			}

			if (ok) ans = max(ans, __builtin_popcount(mask));
		}

		for (auto v: grafo_rev[u])
		{
			if (st.find({grafo[v].size(), v}) == st.end()) continue;

			st.erase({grafo[v].size(), v});

			grafo[v].erase(u);

			st.insert({grafo[v].size(), v});
		}
	}

	printf("%d\n", ans+1);
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:15: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:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d);
   ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:25:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &v);
    ~~~~~^~~~~~~~~~

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