oj.uz

Submission #239920

# Submission time Handle Problem Language Result Execution time Memory
239920 2020-06-17T13:54:36 Z dsjong Friends (BOI17_friends) C++14
20 / 100
 805 ms 2432 KB 
#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){
     ~~~~~~~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory 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

Subtask #2
0 / 37.0

# Verdict Execution time Memory 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 -

Subtask #3
0 / 12.0

# Verdict Execution time Memory 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 -

Subtask #4
0 / 31.0

# Verdict Execution time Memory 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 -