Submission #136808

#	Time	Username	Problem	Language	Result	Execution time	Memory
136808		kdh9949	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	528 ms	20472 KiB

politicaldevelopment

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n, k, d[50010], chk[50010], pro[50010], vs, a[11][11], ans;
set<pii> ss;
vector<int> e[50010], v, cv;
queue<int> q;

int btk(int t){
	if(t == vs) return cv.size();
	int ret = btk(t + 1);
	if(!cv.empty()) for(auto &j : cv) if(!a[j][t]) return ret;
	cv.push_back(t);
	ret = max(ret, btk(t + 1));
	cv.pop_back();
	return ret;
}

int get(int x){
	v.clear();
	v.push_back(x);
	if(e[x].empty()) return 1;
	for(auto &i : e[x]){
		if(!pro[i]) v.push_back(i);
	}
	sort(v.begin(), v.end());
	vs = int(v.size());
	if(vs <= 2) return vs;
	for(int i = 0; i < vs; i++){
		for(int j = 0; j < vs; j++){
			a[i][j] = (ss.find({v[i], v[j]}) != ss.end());
		}
	}
	return btk(0);
}

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1, t; i <= n; i++){
		scanf("%d", &t);
		for(int x; t--; ){
			scanf("%d", &x); x++;
			if(i < x){
				ss.insert({i, x});
				e[i].push_back(x);
				e[x].push_back(i);
				d[i]++; d[x]++;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		if(d[i] < k){
			q.push(i);
			chk[i] = 1;
		}
	}
	for(int t = n - k + 1; t--;){
		int cur = q.front(); q.pop();
		ans = max(ans, get(cur));
		pro[cur] = 1;
		if(!e[cur].empty()){
			for(auto &j : e[cur]){
				d[j]--;
				if(!chk[j] && d[j] < k){
					q.push(j);
					chk[j] = 1;
				}
			}
		}
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:39: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:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t);
   ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:43:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x); x++;
    ~~~~~^~~~~~~~~~

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