oj.uz

Submission #132722

# Submission time Handle Problem Language Result Execution time Memory
132722 2019-07-19T11:51:45 Z imyujin Friends (BOI17_friends) C++14
20 / 100
 86 ms 632 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 15 ms 632 KB Output is correct
5 Correct 76 ms 632 KB Output is correct
6 Correct 81 ms 632 KB Output is correct
7 Correct 86 ms 632 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 15 ms 632 KB Output is correct
5 Correct 76 ms 632 KB Output is correct
6 Correct 81 ms 632 KB Output is correct
7 Correct 86 ms 632 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -