Submission #239847

#	Time	Username	Problem	Language	Result	Execution time	Memory
239847		dsjong	Friends (BOI17_friends)	C++14	0 / 100	1098 ms	512 KiB

friends

#include <bits/stdc++.h>
using namespace std;
bool friends[20][20];
int n, p, q, g;
int cnt[20], deg[20];
vector<int>v;
vector<int>ans[20];
bool good=false;
void go(){
	if(v.size()==n){
		if(ans[0].empty()){
			for(int i=0;i<n;i++) ans[v[i]].push_back(i);
			bool possible=true;
			for(int i=0;i<g;i++){
				//for(int j:ans[i]) cout<<j<<" ";
				//	cout<<": ";
				int tot=0, cnt=0;
				for(int j=0;j<ans[i].size();j++){
					tot+=deg[ans[i][j]];
					for(int k=j+1;k<ans[i].size();k++){
						if(friends[ans[i][j]][ans[i][k]]) cnt+=2;
					}
				}
				int out=tot-cnt;
				//cout<<tot<<" "<<cnt<<" "<<out<<endl;
				if(out>q){
					possible=false;
					for(int i=0;i<g;i++) ans[i].clear();
					break;
				}
			}
			if(possible) good=true;
		}
		return;
	}
	if(good) return;
	for(int i=0;i<g;i++){
		if(cnt[i]<p){
			cnt[i]++;
			v.push_back(i);
			go();
			v.pop_back();
			cnt[i]--;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>p>>q;
	for(int i=0;i<n;i++){
		int m;
		cin>>m;
		deg[i]=m;
		for(int j=0;j<m;j++){
			int x;
			cin>>x;
			friends[i][x]=true;
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(friends[i][j]!=friends[j][i]){
				cout<<"detention";
				return 0;
			}
		}
	}
	memset(cnt, 0, sizeof cnt);
	g=(n+p-1)/p;
	go();
	if(!good) cout<<"detention";
	else{
		cout<<"home\n";
		cout<<g<<"\n";
		for(int i=0;i<g;i++){
			cout<<ans[i].size()<<" ";
			for(int j:ans[i]) cout<<j<<" ";
			cout<<"\n";
		}
	}
}

Compilation message (stderr)

friends.cpp: In function 'void go()':
friends.cpp:10:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(v.size()==n){
     ~~~~~~~~^~~
friends.cpp:18:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<ans[i].size();j++){
                 ~^~~~~~~~~~~~~~
friends.cpp:20:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for(int k=j+1;k<ans[i].size();k++){
                    ~^~~~~~~~~~~~~~

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