oj.uz

Submission #132543

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

vector<vector<int> > ans;
int N, p, q, P[100009];
vector<int> adj[2509];
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) {
		for(auto& it: adj[i]) {
			if(((bit >> it) & 1) == 0) ++ret;
			if(ret > q) return ret;
		}
	}
	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);
	assert(N <= 16);
	for(int i=0; i<N; i++) {
		int m; scanf("%d",&m);
		for(int j=0; j<m; j++) {
			int foo; scanf("%d",&foo);
			adj[i].push_back(foo);
			chk[i][foo] = 1;
		}
	}
	int all = (1<<N) - 1;
	for(int i=1; i<(1<<N); i++) {
		D[i] = ok[i] = (__builtin_popcount(i) <= p && cnt(i) <= q);
		vector<int> S;
		for(int j=0; j<N; j++) if((i >> j) & 1) S.push_back(j);
		for(int k=1; k<(1<<sz(S)); k++) {
			int bit = 0;
			for(int j=0; j<sz(S); j++) if((k >> j) & 1) bit |= (1 << S[j]);
			D[i] |= (D[bit] && D[i ^ bit]);
			if(D[bit] && D[i ^ bit]) P[i] = bit;
			if(D[i]) break;
		}
		// show(i);
		// printf("result: %d\n\n", D[i]);
	}
	for(int i=0; i<N; i++) for(int j=0; j<N; j++) if(chk[i][j] && !chk[j][i]) D[all] = 0;
	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 puts("detention");
	return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:75: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:77: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:46: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:49: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:51: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
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 174 ms 732 KB Output is correct
5 Execution timed out 1071 ms 800 KB Time limit exceeded
6 Halted 0 ms 0 KB -

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 174 ms 732 KB Output is correct
5 Execution timed out 1071 ms 800 KB Time limit exceeded
6 Halted 0 ms 0 KB -