#include <bits/stdc++.h>
using namespace std;
bool friends[20][20], fin[20];
int n, p, q, g;
int cnt[20], deg[20], tot_deg[20];
vector<int>v;
vector<int>ans[20];
bool good=false;
bool dp[1000000], done[1000000];
double start;
bool checkgrp(int grp){
vector<int>vv;
int x=0;
for(int i=0;i<v.size();i++)
if(v[i]==grp){
vv.push_back(i);
x+=(1<<i);
}
if(done[x]) return dp[x];
int tot=0, cc=0;
for(int j=0;j<vv.size();j++){
tot+=deg[vv[j]];
for(int k=j+1;k<vv.size();k++){
if(friends[vv[j]][vv[k]]) cc+=2;
}
}
done[x]=true;
bool ans=(tot-cc<=q);
return dp[x]=(tot-cc<=q);
}
void go(){
double now=clock();
if((now-start)/CLOCKS_PER_SEC > 0.8) return;
if(v.size()==n){
if(ans[0].empty()){
bool possible=true;
for(int i=0;i<g;i++){
if(cnt[i]==p) continue;
if(!checkgrp(i)){
possible=false;
break;
}
}
if(possible){
for(int i=0;i<n;i++) ans[v[i]].push_back(i);
good=true;
}
}
return;
}
if(good) return;
memset(fin, 0, sizeof fin);
for(int i=0;i<g;i++){
if(cnt[i]<p){
if(fin[cnt[i]]) continue;
fin[cnt[i]]=1;
cnt[i]++;
v.push_back(i);
if(cnt[i]==p){
if(checkgrp(i)) go();
}
else go();
v.pop_back();
cnt[i]--;
}
}
}
int main(){
start=clock();
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(done, false, sizeof done);
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
friends.cpp: In function 'bool checkgrp(int)':
friends.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++)
~^~~~~~~~~
friends.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vv.size();j++){
~^~~~~~~~~~
friends.cpp:23:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=j+1;k<vv.size();k++){
~^~~~~~~~~~
friends.cpp:28:7: warning: unused variable 'ans' [-Wunused-variable]
bool ans=(tot-cc<=q);
^~~
friends.cpp: In function 'void go()':
friends.cpp:34:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v.size()==n){
~~~~~~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
16 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
55 ms |
1408 KB |
Output is correct |
| 6 |
Correct |
587 ms |
1280 KB |
Output is correct |
| 7 |
Correct |
805 ms |
1532 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
2432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
7 ms |
2432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 4 |
Correct |
16 ms |
1372 KB |
Output is correct |
| 5 |
Correct |
55 ms |
1408 KB |
Output is correct |
| 6 |
Correct |
587 ms |
1280 KB |
Output is correct |
| 7 |
Correct |
805 ms |
1532 KB |
Output is correct |
| 8 |
Correct |
4 ms |
384 KB |
Output is correct |
| 9 |
Correct |
5 ms |
384 KB |
Output is correct |
| 10 |
Runtime error |
7 ms |
2432 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Halted |
0 ms |
0 KB |
- |
