Submission #241144

#	Time	Username	Problem	Language	Result	Execution time	Memory
241144		super_j6	Friends (BOI17_friends)	C++14	100 / 100	9 ms	896 KiB

friends

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 2500;
int n, x, y;
int id[mxn], in[mxn], ot[mxn], ud[mxn];
vector<int> v;
vector<int> g[mxn];
set<int> s[mxn];
stack<int> stk;
int k, kx, ky;

void die(){
	cout << "detention" << endl;
	exit(0);
}

//branch group
void spush(int c){
	ud[c] = 1;
	stk.push(c);
}

int spop(){
	int c = stk.top();
	stk.pop();
	ud[c] = 0;
	return c;
}

bool sol(), solin(), solout();

bool sol(){
	if(kx > x || ky > y || kx + ky + stk.size() > x + y) return 0;
	if(stk.empty()) return 1;
	return solin() || solout();
}

bool solin(){
	int c = spop();
	
	int m = 0;
	kx++, in[c] = 1;
	for(int i : g[c]){
		ky += ot[i];
		if(in[i] || ot[i] || ud[i]) continue;
		m++;
		spush(i);
	}
	
	bool ret = sol();
	
	kx--, in[c] = 0;
	for(int i : g[c]) ky -= ot[i];
	while(m--) spop();
	spush(c);
	
	if(ret)	s[k].insert(c);
	
	return ret;
}

bool solout(){
	int c = spop();
	
	ot[c] = 1;
	for(int i : g[c]) ky += in[i];
	
	bool ret = sol();
	
	ot[c] = 0;
	for(int i : g[c]) ky -= in[i];
	spush(c);
	
	return ret;
}
//end branch group

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> x >> y;
	
	for(int i = 0; i < n; i++){
		int m;
		cin >> m;
		for(int j = 0; j < m; j++){
			int v;
			cin >> v;
			g[i].push_back(v);
		}
		sort(g[i].begin(), g[i].end());
	}
	
	for(int i = 0; i < n; i++){
		id[i] = -1;
		for(int j : g[i]){
			auto it = lower_bound(g[j].begin(), g[j].end(), i);
			if(it == g[j].end() || *it != i) die();
		}
	}
	
	int ret = 0;
	for(; k < n; k++){
		if(~id[k]) continue;
		
		ret++;
		spush(k);
		if(!solin()) die();
		spop();
		
		loop:
		for(int i : s[k]){
			int m = id[i];
			if(~m && m != k){
				//fix group
				v.clear();
				for(int j  : s[k]){
					if(id[j] == m){
						v.push_back(j);
						s[m].erase(j);
						id[j] = k;
					} 
				} 
				
				int f = 0;
				for(int j : s[m])
				for(int l : g[j]){
					f += !s[m].count(l);
				}
				
				if(f > y){
					for(int j : v){
						id[j] = m;
						s[m].insert(j);
						s[k].erase(j);
					}
					goto loop;
				}else{
					ret -= s[m].empty();
				}
			}else{
				id[i] = k;
			}
		}
	}
	
	cout << "home" << endl;
	
	cout << ret << endl;
	for(int i = 0; i < k; i++){
		if(s[i].empty()) continue;
		cout << s[i].size();
		for(int j : s[i]) cout << " " << j;
		cout << endl;
	}

	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'bool sol()':
friends.cpp:44:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(kx > x || ky > y || kx + ky + stk.size() > x + y) return 0;
                         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 37 / 37
• Subtask 3: 12 / 12
• Subtask 4: 31 / 31