Submission #727241

#	Time	Username	Problem	Language	Result	Execution time	Memory
727241		gagik_2007	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	664 ms	60492 KiB

politicaldevelopment

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <chrono>
#include <ctime>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <limits>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <functional>
#include <random>
#include <cassert>
using namespace std;

typedef long long ll;
typedef long double ld;

#define ff first
#define ss second

ll ttt;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const ll N = 500007;
ll n, m, k;
vector<int>g[N];
int deg[N];
bool used[N];
unordered_map<ll, bool>d;
int vs[N];

ll value(int v, int u) {
	return v * N + u;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> m;
		deg[i] = m;
		for (int j = 0; j < m; j++) {
			int x;
			cin >> x;
			g[i].push_back(x);
			d[value(i, x)] = true;
		}
	}
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
	for (int v = 0; v < n; v++) {
		q.push({ deg[v],v });
	}
	ll ans = 0;
	while (!q.empty()) {
		int v = q.top().ss;
		q.pop();
		//cout << v << ": " << deg[v] << endl;
		if (!used[v]) {
			int ind = 0;
			for (int i = 0; i < g[v].size(); i++) {
				if (!used[g[v][i]]) {
					vs[ind] = g[v][i];
					ind++;
				}
			}
			for (int msk = 0; msk < (1 << deg[v]); msk++) {
				ll cnt = 1;
				bool ok = true;
				for (int i = 0; i < deg[v]; i++) {
					if (msk & (1 << i)) {
						cnt++;
					}
					for (int j = i + 1; j < deg[v]; j++) {
						if (msk & (1 << j)) {
							if (!d[value(vs[i], vs[j])]) {
								ok = false;
								break;
							}
						}
					}
				}
				if (ok) {
					ans = max(ans, cnt);
				}
			}
			used[v] = true;
			for (int u : g[v]) {
				deg[u]--;
				q.push({ deg[u],u });
			}
		}
	}
	cout << ans << endl;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for (int i = 0; i < g[v].size(); i++) {
      |                    ~~^~~~~~~~~~~~~

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