Submission #132722

#	Time	Username	Problem	Language	Result	Execution time	Memory
132722		imyujin	Friends (BOI17_friends)	C++14	20 / 100	86 ms	632 KiB

friends

#include <bits/stdc++.h>
using namespace std;

#define rb(x) ((x) & (-(x)))

bool ed[16][16];
bool P[70000], D[70000];
int W[70000];

int main() {
	int N, p, q;
	int m, u;

	scanf("%d%d%d", &N, &p, &q);
	for(int i = 0; i < N; i++) {
		scanf("%d", &m);
		while(m--) {
			scanf("%d", &u);
			ed[i][u] = true;
		}
	}

	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) if(int(ed[i][j]) + int(ed[j][i]) == 1) {
		printf("detention");
		return 0;
	}

	for(int i = 0; i < (1 << N); i++) {
		int cntp = 0, cntq = 0;
		for(int j = 0; j < N; j++) if((1 << j) & i) {
			cntp++;
			for(int k = 0; k < N; k++) if(ed[j][k] && ((1 << k) & i) == 0) cntq++;
		}
		P[i] = cntp <= p && cntq <= q;
		//if(P[i]) printf("%d\n", i);
	}

	D[0] = true;
	for(int i = 1; i < (1 << N); i++) {
		D[i] = P[i];
		for(int j = i & (i - 1); j != 0 && !D[i]; j = (j - 1) & i) if(D[j] && P[i - j]) {
			D[i] = true;
			W[i] = j;
			//printf("i = %d, j = %d = %d\n", i, j, W[i]);
		}
		//if(D[i]) printf("W[%d] = %d\n", i, W[i]);
	}

	if(!D[(1 << N) - 1]) printf("detention");
	else {
		printf("home\n");
		vector<int> ans = { (1 << N) - 1 };
		while(ans.back() != 0) ans.push_back(W[ans.back()]);
		printf("%d\n", int(ans.size()) - 1);
		//for(auto a : ans) printf("%d\n", a);
		for(int i = 1; i < ans.size(); i++) {
			vector<int> v;
			for(int j = 0; j < N; j++) if((ans[i - 1] - ans[i]) & (1 << j)) v.push_back(j);
			printf("%lu ", v.size());
			for(auto a : v) printf("%d ", a);
			printf("\n");
		}
	}
	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'int main()':
friends.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
friends.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &p, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
friends.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
friends.cpp:18:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &u);
    ~~~~~^~~~~~~~~~

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