Submission #239920

#TimeUsernameProblemLanguageResultExecution timeMemory
239920dsjongFriends (BOI17_friends)C++14
20 / 100
805 ms2432 KiB
#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 (stderr)

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){
     ~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...