oj.uz

Submission #414663

# Submission time Handle Problem Language Result Execution time Memory
414663 2021-05-31T02:25:01 Z 8e7 Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 8 ms 4092 KB 
//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++) {
		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

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++) {
      |                 ~~^~~~~~~~~~~
politicaldevelopment.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for (int j = i;j < se.size();j++) {
      |                  ~~^~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3060 KB Output is correct
3 Correct 7 ms 4044 KB Output is correct
4 Correct 8 ms 4092 KB Output is correct
5 Correct 6 ms 4044 KB Output is correct
6 Correct 7 ms 4044 KB Output is correct
7 Correct 7 ms 4044 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Incorrect 4 ms 3148 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3060 KB Output is correct
3 Correct 7 ms 4044 KB Output is correct
4 Correct 8 ms 4092 KB Output is correct
5 Correct 6 ms 4044 KB Output is correct
6 Correct 7 ms 4044 KB Output is correct
7 Correct 7 ms 4044 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Incorrect 4 ms 3148 KB Output isn't correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3068 KB Output is correct
2 Incorrect 3 ms 3020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3060 KB Output is correct
3 Correct 7 ms 4044 KB Output is correct
4 Correct 8 ms 4092 KB Output is correct
5 Correct 6 ms 4044 KB Output is correct
6 Correct 7 ms 4044 KB Output is correct
7 Correct 7 ms 4044 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Incorrect 4 ms 3148 KB Output isn't correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3020 KB Output is correct
2 Correct 3 ms 3060 KB Output is correct
3 Correct 7 ms 4044 KB Output is correct
4 Correct 8 ms 4092 KB Output is correct
5 Correct 6 ms 4044 KB Output is correct
6 Correct 7 ms 4044 KB Output is correct
7 Correct 7 ms 4044 KB Output is correct
8 Correct 3 ms 3148 KB Output is correct
9 Correct 3 ms 3020 KB Output is correct
10 Incorrect 4 ms 3148 KB Output isn't correct