| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 239874 |
2020-06-17T12:34:30 Z |
dsjong |
Friends (BOI17_friends) |
C++14 |
|
5 ms |
512 KB |
#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;
bool dp[1000000], done[1000000];
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, cnt=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]]) cnt+=2;
}
}
done[x]=true;
return dp[x]=(tot-cnt<=q);
}
void go(){
if(v.size()==n){
//for(int i:v) cout<<i<<" ";
// cout<<endl;
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;
for(int i=0;i<g;i++){
if(cnt[i]==p){
if(!checkgrp(i)) return;
}
}
for(int i=0;i<g;i++){
if(v.size()==0 && i>0) break;
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
friends.cpp: In function 'bool checkgrp(int)':
friends.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++)
~^~~~~~~~~
friends.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<vv.size();j++){
~^~~~~~~~~~
friends.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=j+1;k<vv.size();k++){
~^~~~~~~~~~
friends.cpp: In function 'void go()':
friends.cpp:30:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v.size()==n){
~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
