oj.uz

Submission #132577

# Submission time Handle Problem Language Result Execution time Memory
132577 2019-07-19T07:39:42 Z 이온조(#3199) Friends (BOI17_friends) C++14
20 / 100
 15 ms 760 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define sz(V) ((int)V.size())

void fail() {
	puts("detention");
	exit(0);
}

vector<vector<int> > ans;
int N, p, q, P[100009], all;
vector<int> adj[2509];
int ba[22];
bool D[100009], ok[100009], chk[2509][2509];

int cnt(int bit) {
	int ret = 0;
	for(int i=0; i<N; i++) if((bit >> i) & 1) ret += __builtin_popcount((all ^ bit) & ba[i]);
	return ret;
}

void Do(int bit) {
	vector<int> S;
	for(int i=0; i<N; i++) if((bit >> i) & 1) S.push_back(i);
	ans.push_back(S);
}

void go(int bit) {
	if(ok[bit]) {
		Do(bit);
		return;
	}
	go(P[bit]);
	go(P[bit] ^ bit);
}

void show(int bit) {
	for(int i=0; i<N; i++) {
		if((bit >> i) & 1) printf("1");
		else printf("0");
	}
	puts("");
}

int main() {
	scanf("%d%d%d",&N,&p,&q);
	// N = 16; p = 15; q = 0;
	all = (1<<N) - 1;
	assert(N <= 16);
	for(int i=0; i<N; i++) {
		int m; scanf("%d",&m);
		// int m = 0;
		for(int j=0; j<m; j++) {
			int foo; scanf("%d",&foo);
			adj[i].push_back(foo);
			chk[i][foo] = 1;
			ba[i] |= (1 << foo);
		}
	}
	for(int i=0; i<N; i++) for(int j=0; j<N; j++) if(chk[i][j] && !chk[j][i]) fail();
	int S[22];
	for(int i=1; i<(1<<N); i++) {
		D[i] = ok[i] = (__builtin_popcount(i) <= p && cnt(i) <= q);
		int c = 0;
		for(int j=0; j<N; j++) if((i >> j) & 1) S[c++] = j;
		for(int k=1; k<c; k++) {
			int bit = 0;
			for(int j=0; j<c; j++) if((k >> j) & 1) bit |= (1 << S[j]);
			D[i] |= (ok[bit] && D[i ^ bit]);
			if(ok[bit] && D[i ^ bit]) P[i] = bit;
			if(D[i]) break;
		}
		// show(i);
		// printf("result: %d\n\n", D[i]);
	}
	if(D[all]) {
		puts("home");
		go(all);
		printf("%d\n", ans.size());
		for(auto& it: ans) {
			printf("%d ", it.size());
			for(auto& jt: it) printf("%d ", jt);
			puts("");
		}
	}
	else fail();
	return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:80:28: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::vector<int> >::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n", ans.size());
                  ~~~~~~~~~~^
friends.cpp:82:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
    printf("%d ", it.size());
                  ~~~~~~~~~^
friends.cpp:47: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:52:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int m; scanf("%d",&m);
          ~~~~~^~~~~~~~~
friends.cpp:55:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int foo; scanf("%d",&foo);
             ~~~~~^~~~~~~~~~~

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 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 13 ms 760 KB Output is correct
6 Correct 15 ms 632 KB Output is correct
7 Correct 14 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 632 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 632 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 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 13 ms 760 KB Output is correct
6 Correct 15 ms 632 KB Output is correct
7 Correct 14 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 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -