Submission #414665

#	Time	Username	Problem	Language	Result	Execution time	Memory
414665		8e7	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	198 ms	26880 KiB

politicaldevelopment

//Challenge: Accepted
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <cmath>
#include <assert.h>
#include <unordered_set>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template <class T, class ...U> void debug(T a, U ... b) { cout << a << " "; debug(b...);}
template <class T> void pary(T l, T r) {
	while (l != r) {cout << *l << " ";l++;}
	cout << endl;
}
#define ll long long
#define ld long double
#define maxn 50005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
unordered_set<int> ed[maxn];
int ord[maxn], deg[maxn], found[maxn], g[15];
int ans = 0;
int getans(int s, int cur, int ind, int se) {
	if (ind >= s) return 0;
	int ret = 0;
	for (int v = ind;v < s;v++) {
		if (((g[v] & se) & (cur | (1<<v))) == (cur | (1<<v))) {
			ret = max(ret, getans(s, cur | (1<<v), v + 1, g[v] & se) + 1);
		}
	}
	return ret;
}
void solve(int n) {
	vector<int> se;
	se.push_back(n);
	for (int v:ed[n]) {
		if (!found[v]) se.push_back(v);
	}	
	//pary(se.begin(), se.end());
	if (se.size() <= ans) return;
	for (int i = 0;i < se.size();i++) g[i] = 0;
	for (int i = 0;i < se.size();i++) {
		for (int j = i;j < se.size();j++) {
			if (i == j) g[i] += 1<<i;
			else {
				int v = ed[se[i]].find(se[j]) == ed[se[i]].end() ? 0 : 1;
				//debug(se[i], se[j], v);
				g[i] += (1<<j) * v;
				g[j] += (1<<i) * v;
			}
		}
	}
	//pary(g, g + se.size());
	ans = max(ans, getans(se.size(), 0, 0, (1<<se.size()) - 1));	
}
int main() {
	io
	int n, k;
	cin >> n >> k;
	for (int i = 0;i < n;i++) {
		int di;
		cin >> di;
		deg[i] = di;
		for (int j = 0;j < di;j++) {
			int x;cin >> x;
			ed[i].insert(x);
		}
	}
	queue<int> que;
	for (int i = 0;i < n;i++) {
		if (deg[i] < k) {
			que.push(i); found[i] = 1;
		}
	}
	int ind = 0;
	while (que.size()) {
		int cur = que.front();que.pop();
		ord[ind++] = cur;
		for (int v:ed[cur]) {
			if (--deg[v] < k && !found[v]) {
				que.push(v);found[v] = 1;
			}
		}
	}
	for (int i = 0;i < n;i++) found[i] = 0;
	for (int i = 0;i < n;i++) solve(ord[i]), found[ord[i]] = 1;
	cout << ans << endl;
}
/*
5 3
2 1 2
3 0 2 3
3 0 1 4
2 1 4
2 2 3

*/

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void solve(int)':
politicaldevelopment.cpp:49:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |  if (se.size() <= ans) return;
      |      ~~~~~~~~~~^~~~~~
politicaldevelopment.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0;i < se.size();i++) g[i] = 0;
      |                 ~~^~~~~~~~~~~
politicaldevelopment.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i = 0;i < se.size();i++) {
      |                 ~~^~~~~~~~~~~
politicaldevelopment.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j = i;j < se.size();j++) {
      |                  ~~^~~~~~~~~~~

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