Submission #197159

#	Time	Username	Problem	Language	Result	Execution time	Memory
197159		dndhk	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	972 ms	31652 KiB

politicaldevelopment

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1000000000;
const int MAX_N = 50000;
const int MAX_K = 10;

int N, K;
vector<int> gp[MAX_N+1];
bool chk[MAX_N+1];
int deg[MAX_N+1];

priority_queue<pii, vector<pii>, greater<pii> > pq;
vector<int> vt;
int ans, idx;
vector<int> v;
set<pii> st;

void calc(int x){
	if(x==vt.size()){
		for(int i=0; i<v.size(); i++){
			for(int j=i+1; j<v.size(); j++){
				if(st.find({v[i], v[j]})==st.end())	return;
			}
		}
		ans = max(ans, (int)v.size());
		return;
	}else{
		calc(x+1);
		v.pb(vt[x]);
		calc(x+1);
		v.pop_back();
	}
}

int main(){
	scanf("%d%d", &N, &K);
	for(int i=0; i<N; i++){
		int x, y; scanf("%d", &x);
		deg[i] = x;
		while(x--){
			scanf("%d", &y);
			st.insert({i, y});
			gp[i].pb(y);
		}
		pq.push({deg[i], i});
	}
	while(!pq.empty()){
		pii now = pq.top(); pq.pop();
		if(chk[now.second])	continue;
		idx = now.second;
		chk[idx] = true;
		while(!vt.empty())	vt.pop_back();
		for(int i : gp[idx]){
			if(!chk[i]){
				vt.pb(i);
			}
		}
		while(!v.empty())	v.pop_back();
		v.pb(idx);
		calc(0);
		for(int i : gp[idx]){
			if(!chk[i]){
				deg[i]--;
				pq.push({deg[i], i});
			}
		}
	}
	cout<<ans;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void calc(int)':
politicaldevelopment.cpp:27:6: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(x==vt.size()){
     ~^~~~~~~~~~~
politicaldevelopment.cpp:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++){
                ~^~~~~~~~~
politicaldevelopment.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=i+1; j<v.size(); j++){
                   ~^~~~~~~~~
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:44: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:46:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d", &x);
             ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:49:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &y);
    ~~~~~^~~~~~~~~~

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