Submission #1254328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254328		kaiboy	Friends (BOI17_friends)	C++20	100 / 100	154 ms	16724 KiB

friends

// coached by rainboy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 2500;

bool aa[N][N];
vector<int> ej[N];
bool visited[N], used[N];
int qu[N], cnt, c, d, s;
int ii[N][N], kk[N], ii_[N];
int n, c_, s_;

bool solve() {
	if (c <= c_ && s <= s_)
		return true;
	if (c > c_ || d > s_)
		return false;
	int i = -1;
	for (int h = 0; h < cnt; h++)
		if (!visited[qu[h]]) {
			i = qu[h];
			break;
		}
	if (i == -1)
		return false;
	visited[i] = used[i] = true, c++;
	for (int j : ej[i]) {
		qu[cnt++] = j;
		if (used[j])
			s--;
		else
			s++;
	}
	if (solve())
		return true;
	used[i] = false, c--, d++;
	for (int j : ej[i]) {
		cnt--;
		if (used[j])
			s++;
		else
			s--;
	}
	if (solve())
		return true;
	visited[i] = false, d--;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> c_ >> s_;
	for (int i = 0; i < n; i++) {
		int d; cin >> d;
		if (d > c_ + s_) {
			cout << "detention\n";
			return 0;
		}
		while (d--) {
			int j; cin >> j;
			aa[i][j] = true;
			ej[i].push_back(j);
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (aa[i][j] != aa[j][i]) {
				cout << "detention\n";
				return 0;
			}
	for (int i_ = 0; i_ < n; i_++) {
		for (int i = 0; i < n; i++)
			visited[i] = used[i] = false;
		c = d = s = 0;
		visited[i_] = used[i_] = true, c++, cnt = 0;
		for (int j : ej[i_])
			qu[cnt++] = j, s++;
		if (!solve()) {
			cout << "detention\n";
			return 0;
		}
		for (int i = 0; i < n; i++)
			if (used[i])
				ii[i_][kk[i_]++] = i;
	}
	for (int l = 0; l < n; l++)
		for (int r = l + 1; r < n; r++) {
			int kl = kk[l], kr = kk[r], k = 0;
			for (int hl = 0, hr = 0; hl < kl && hr < kr; ) {
				int il = ii[l][hl], ir = ii[r][hr];
				if (il < ir)
					hl++;
				else if (il > ir)
					hr++;
				else
					ii_[k++] = il, hl++, hr++;
			}
			if (!k)
				continue;
			int sl = 0, sr = 0;
			for (int h = 0; h < k; h++) {
				int i = ii_[h];
				for (int hl = 0; hl < kl; hl++)
					if (aa[i][ii[l][hl]])
						sl++;
				for (int hr = 0; hr < kr; hr++)
					if (aa[i][ii[r][hr]])
						sr++;
			}
			if (sl < sr) {
				int kl_ = 0;
				for (int hl = 0; hl < kl; hl++) {
					int il = ii[l][hl];
					bool yes = true;
					for (int h = 0; h < k; h++)
						if (il == ii_[h]) {
							yes = false;
							break;
						}
					if (yes)
						ii[l][kl_++] = il;
				}
				kk[l] = kl_;
			} else {
				int kr_ = 0;
				for (int hr = 0; hr < kr; hr++) {
					int ir = ii[r][hr];
					bool yes = true;
					for (int h = 0; h < k; h++)
						if (ir == ii_[h]) {
							yes = false;
							break;
						}
					if (yes)
						ii[r][kr_++] = ir;
				}
				kk[r] = kr_;
			}
		}
	int m = 0;
	for (int i = 0; i < n; i++)
		if (kk[i])
			m++;
	cout << "home\n";
	cout << m << '\n';
	for (int i = 0; i < n; i++) {
		int k = kk[i];
		if (k) {
			cout << k;
			for (int h = 0; h < k; h++)
				cout << ' ' << ii[i][h];
			cout << '\n';
		}
	}
	return 0;
}

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