oj.uz

Submission #235082

# Submission time Handle Problem Language Result Execution time Memory
235082 2020-05-27T01:05:27 Z luciocf Political Development (BOI17_politicaldevelopment) C++14
4 / 100
 16 ms 6272 KB 
#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[i].find(j) == grafo[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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 16 ms 6272 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 16 ms 6272 KB Output is correct
7 Correct 15 ms 6272 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 16 ms 6272 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 16 ms 6272 KB Output is correct
7 Correct 15 ms 6272 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 14 ms 6272 KB Output is correct
12 Correct 14 ms 6272 KB Output is correct
13 Incorrect 7 ms 4992 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5248 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Incorrect 7 ms 4992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 16 ms 6272 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 16 ms 6272 KB Output is correct
7 Correct 15 ms 6272 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 14 ms 6272 KB Output is correct
12 Correct 14 ms 6272 KB Output is correct
13 Incorrect 7 ms 4992 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 16 ms 6272 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 14 ms 6272 KB Output is correct
6 Correct 16 ms 6272 KB Output is correct
7 Correct 15 ms 6272 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 7 ms 4992 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 14 ms 6272 KB Output is correct
12 Correct 14 ms 6272 KB Output is correct
13 Incorrect 7 ms 4992 KB Output isn't correct
14 Halted 0 ms 0 KB -