oj.uz

Submission #547548

# Submission time Handle Problem Language Result Execution time Memory
547548 2022-04-10T23:16:20 Z skittles1412 Friends (BOI17_friends) C++17
37 / 100
 81 ms 1752 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 2505;

//#define STRESS

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

void print(const vector<vector<int>>& ans) {
#ifndef STRESS
	cout << sz(ans) << endl;
	for (auto& a : ans) {
		cout << sz(a);
		for (auto& b : a) {
			cout << " " << b;
		}
		cout << endl;
	}
#endif
}

bool found;
int n, p, q, cp, cq, decided[maxn];
vector<int> graph[maxn], cans, incl;

void dfs() {
	if (found || cp > p || cq > q) {
		return;
	}
	for (auto& a : incl) {
		for (auto& v : graph[a]) {
			if (!decided[v]) {
				{
					cp++;
					decided[v] = 1;
					incl.push_back(v);
					dfs();
					incl.pop_back();
					decided[v] = 0;
					cp--;
				}
				{
					cq++;
					decided[v] = -1;
					dfs();
					decided[v] = 0;
					cq--;
				}
				return;
			}
		}
	}
	cans = incl;
	found = true;
}

void solve() {
	cin >> n >> p >> q;
	for (int i = 0; i < n; i++) {
		auto& a = graph[i];
		int m;
		cin >> m;
		if (m > p + q - 1) {
			fail();
		}
		a.resize(m);
		for (auto& b : a) {
			cin >> b;
		}
	}
	for (int i = 0; i < n; i++) {
		for (auto& v : graph[i]) {
			auto& gv = graph[v];
			if (find(begin(gv), end(gv), i) == gv.end()) {
				fail();
			}
		}
	}
	set<int> blocks[n];
	for (int i = 0; i < n; i++) {
		incl = {i};
		decided[i] = 1;
		cp = 1;
		cq = 0;
		found = false;
		dfs();
		decided[i] = 0;
		if (!found) {
			fail();
		}
		blocks[i].insert(begin(cans), end(cans));
		dbg(i);
		for (auto& a : blocks[i]) {
			cerr << a << " ";
		}
		cerr << endl;
	}
	auto excl = [&](set<int> a, const set<int> &b) -> set<int> {
		for (auto& x : b) {
			a.erase(x);
		}
		return a;
	};
	auto check = [&](const set<int> &arr) -> bool {
		static int vis[maxn] {}, vind = 0;
		vind++;
		if (sz(arr) > p) {
			return false;
		}
		int cnt = 0;
		for (auto& a : arr) {
			vis[a] = vind;
		}
		for (auto& a : arr) {
			for (auto& b : graph[a]) {
				if (vis[b] != vind) {
					vis[b] = vind;
					if (++cnt > q) {
						return false;
					}
				}
			}
		}
		return true;
	};
	for (int i = 0; i < n; i++) {
		auto &a = blocks[i];
		for (int j = i + 1; j < n; j++) {
			auto &b = blocks[j];
			auto x = excl(a, b);
			if (check(x)) {
				a = x;
			} else {
				b = excl(b, a);
				assert(check(b));
			}
		}
	}
	vector<vector<int>> ans;
	for (auto& a : blocks) {
		assert(check(a));
		if (sz(a)) {
			ans.emplace_back(begin(a), end(a));
		}
	}
	cout << "home" << endl;
	print(ans);
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
	solve();
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 392 KB Output is correct
2 Correct 4 ms 392 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 6 ms 468 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 392 KB Output is correct
2 Correct 4 ms 392 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 74 ms 852 KB Output is correct
11 Runtime error 81 ms 1752 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 0 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -