Submission #241139

#	Time	Username	Problem	Language	Result	Execution time	Memory
241139		super_j6	Friends (BOI17_friends)	C++14	69 / 100	1087 ms	32084 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

bool is(const set<int> &s) {
	//printf("is valid group:\n");
	//printSet(s);
 
	int cnt = 0;
	if(s.empty()) return true;
	for(set<int>::iterator itr = s.begin(); itr != s.end(); ++itr) {
		int u = *itr;
		//printf("vertex u: %d\n", u);
		for(int i = 0; i < g[u].size(); ++i) {
			int v = g[u][i];
			cnt += (s.count(g[u][i]) == 0 ? 1 : 0);
			//printf("vertex v: %d   count: %d\n", v, cnt);
		}
	}
	//printf("answer is %d\n", (cnt <= q ? 1 : 0));
	return cnt <= y;
}

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);
						id[j] = -1;
					} 
				} 
				
				int w = 0, z = 0;
				for(int j : v)
				for(int l : g[j]){
					w += id[l] == k;
					z += id[l] == m;
				}
				
				if(w < z){
					for(int j : v){
						id[j] = m;
						s[k].erase(j);
					}
					if(!is(s[k]) || !is(s[m])) while(1) cout << 1 << endl;
					goto loop;
				}else{
					for(int j : v){
						id[j] = k;
						s[m].erase(j);
					}
					ret -= s[m].empty();
					if(!is(s[k]) || !is(s[m])) while(1) cout << 1 << endl;
				}
			}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;
                         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~
friends.cpp: In function 'bool is(const std::set<int>&)':
friends.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[u].size(); ++i) {
                  ~~^~~~~~~~~~~~~
friends.cpp:99:8: warning: unused variable 'v' [-Wunused-variable]
    int v = g[u][i];
        ^

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