제출 #239874

#제출 시각아이디문제언어결과실행 시간메모리
239874dsjongFriends (BOI17_friends)C++14
0 / 100
5 ms512 KiB
#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"; } } }

컴파일 시 표준 에러 (stderr) 메시지

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