Submission #472587

#	Time	Username	Problem	Language	Result	Execution time	Memory
472587		Hamed5001	Political Development (BOI17_politicaldevelopment)	C++14	4 / 100	5 ms	1612 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 5e4;
vector<int> adj[mxN];
map<int, int> freq;
bool vis[mxN];
int N, K;


bool can(int k) {
	vector<pair<int, int>> freq(N, pair<int, int>(0, -1));
	for (int i = 0; i < N; i++) {
		if (adj[i].size()+1 < k)
			continue;
		for (int msk = 0; msk < (1<<adj[i].size()); msk++) {
			if (__builtin_popcount(msk) != k-1)
				continue;
			for (int j = 0; j < adj[i].size(); j++) {
				if ((1<<j) & msk) {
					for (int k = 0; k < adj[adj[i][j]].size(); k++) {
						if (freq[adj[adj[i][j]][k]].second != i)
							freq[adj[adj[i][j]][k]].second = i, freq[adj[adj[i][j]][k]].first = 0;
						freq[adj[adj[i][j]][k]].first++;
					}
				}
  			}
		}
		if (freq[i].first != k-1)
			continue;
		for (auto it : adj[i])
			if (freq[it].first != k-1)
				continue;
		return 1;
	}
	return 0;
}

void solve() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int D;
		cin >> D;
		while(D--) {
			int v;
			cin >> v;
			adj[i].push_back(v);
		}
	}
	for (int i = K; i >= 2; i--)
		if (can(i))
			return void(cout << i);
	cout << 1;
}

int main() {

	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'bool can(int)':
politicaldevelopment.cpp:16:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   16 |   if (adj[i].size()+1 < k)
      |       ~~~~~~~~~~~~~~~~^~~
politicaldevelopment.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |    for (int j = 0; j < adj[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |      for (int k = 0; k < adj[adj[i][j]].size(); k++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~

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