Submission #133386

#	Time	Username	Problem	Language	Result	Execution time	Memory
133386		youngyojun	Friends (BOI17_friends)	C++11	20 / 100	3 ms	508 KiB

friends

#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
void fuk() { puts("detention"); exit(0); }

vector<int> G[2505], W[2505];
int WI[2505];

bitset<2505> chk, isT;
int T[22], Tn;
int E[555], En;

int N, CP, CQ;

void prtSet() {
	int n = 0;
	for(int i = 0; i < N; i++) if(!W[i].empty()) n++;
	puts("home");
	printf("%d\n", n);
	for(int i = 0; i < N; i++) if(!W[i].empty()) {
		printf("%d", sz(W[i]));
		for(int w : W[i]) printf(" %d", w);
		puts("");
	}
}

void normSet() {
	memset(WI, -1, N<<2);
	isT.reset();
	for(int i = 0; i < N; i++) {
		chk.reset();
		for(int w : W[i]) chk[w] = true;
		for(int j = 0; j < i; j++) {
			Tn = 0;
			for(int w : W[i]) if(WI[w] == j) {
				T[Tn++] = w;
				isT[w] = true;
			}
			if(!Tn) continue;
			int c1 = 0, c2 = 0;
			for(int ti = Tn, v; ti--;) {
				v = T[ti];
				for(int u : G[v]) if(!isT[u]) {
					if(chk[u]) c1++;
					else if(WI[u] == j) c2++;
				}
			}
			if(c1 <= c2) {
				for(int v; Tn--;) {
					v = T[Tn];
					isT[v] = chk[v] = false;
				}
				vector<int> V;
				for(int w : W[i]) if(chk[w]) V.eb(w);
				swap(W[i], V);
			} else {
				for(int v; Tn--;) {
					v = T[Tn];
					isT[v] = false;
					WI[v] = -1;
				}
				vector<int> V;
				for(int w : W[j]) if(WI[w] == j) V.eb(w);
				swap(W[j], V);
			}
		}
		for(int w : W[i]) WI[w] = i;
	}
}

bool isGood() {
	int r = 0;
	for(int i = Tn, v; i--;) {
		v = T[i];
		for(int u : G[v]) if(!isT[u]) {
			r++;
			if(CQ < r) return false;
		}
	}
	return true;
}

int dfsleft;
bool dfs(int ei, int lefte) {
	if(dfsleft < 0) fuk();
	dfsleft--;
	if(ei == En) return false;
	int a = E[ei], b = a & 4095; a >>= 12;
	chk[b] = true;
	if(lefte && dfs(ei+1, lefte-1)) return true;
	if(Tn == CP) return false;
	T[Tn++] = b;
	isT[b] = true;
	if(isGood()) return true;
	int pvEn = En;
	for(int v : G[b]) {
		if(chk[v]) {
			if(!isT[v]) {
				if(!lefte) {
					En = pvEn;
					Tn--;
					isT[b] = false;
					return false;
				}
				lefte--;
			}
			continue;
		}
		E[En++] = b<<12 | v;
	}
	if(dfs(ei+1, lefte)) return true;
	En = pvEn;
	Tn--;
	isT[b] = false;
	return false;
}

void findW(int rt) {
	if(sz(G[rt]) <= CQ) {
		W[rt].eb(rt);
		return;
	}
	dfsleft = 1<<16;
	chk.reset(); isT.reset();
	Tn = 1; En = 0;
	T[0] = rt;
	chk[rt] = isT[rt] = true;
	for(int v : G[rt]) E[En++] = rt<<12 | v;
	if(!dfs(0, CQ)) fuk();
	for(; Tn--;) W[rt].eb(T[Tn]);
}

void input() {
	ios::sync_with_stdio(false);
	unordered_map<int, int> MP;
	cin >> N >> CP >> CQ;
	for(int i = 0, dg; i < N; i++) {
		cin >> dg;
		for(int c; dg--;) {
			cin >> c;
			G[i].eb(c);
			MP[i < c ? (i<<12|c) : (c<<12|i)]++;
		}
	}
	for(auto &v : MP) if(2 != v.second) fuk();
	for(int i = 0; i < N; i++) {
		if(CP + CQ <= sz(G[i])) fuk();
		shuffle(allv(G[i]), mt19937(time(0)));
	}
}

int main() {
	input();
	for(int i = 0; i < N; i++) findW(i);
	normSet();
	prtSet();
	return 0;
}

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