Submission #289116

#	Time	Username	Problem	Language	Result	Execution time	Memory
289116		TadijaSebez	Friends (BOI17_friends)	C++11	100 / 100	420 ms	11008 KiB

friends

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=2550;
vector<int> E[N],cmp[N];
stack<int> cns;
bool in[N],in_stk[N],done[N];
int p,q,a,b;
void cl(){for(int i=0;i<N;i++)in[i]=in_stk[i]=done[i]=0;a=b=0;cns=stack<int>();}
bool BCK(int idx){
	if(a>p||b>q||a+b+cns.size()>p+q)return 0;
	if(cns.empty())return 1;
	int u=cns.top();cns.pop();
	a++;in[u]=1;in_stk[u]=0;done[u]=1;
	int cnt=0;
	for(int v:E[u]){
		if(done[v]&&!in[v])b++;
		if(!done[v]&&!in_stk[v]){
			cns.push(v);
			in_stk[v]=1;
			cnt++;
		}
	}
	if(BCK(idx)){
		cmp[idx].pb(u);
		return 1;
	}
	a--;
	in[u]=0;
	for(int v:E[u])if(done[v]&&!in[v])b--;
	while(cnt--)in_stk[cns.top()]=0,cns.pop();
	for(int v:E[u])if(in[v])b++;
	if(BCK(idx)){
		return 1;
	}
	for(int v:E[u])if(in[v])b--;
	done[u]=0;
	in_stk[u]=1;
	cns.push(u);
	return 0;
}
void Fix(int A,int B){
	if(cmp[A].empty()||cmp[B].empty())return;
	set<int> F,S,same;
	for(int i:cmp[A])F.insert(i);
	for(int i:cmp[B]){
		S.insert(i);
		if(F.count(i))same.insert(i),F.erase(i);
	}
	if(same.empty())return;
	int cnt=0;
	for(int i:F)
		for(int j:E[i])
			if(!F.count(j))
				cnt++;
	if(cnt>q){
		for(int i:same)F.insert(i),S.erase(i);
	}
	cmp[A].clear();for(int i:F)cmp[A].pb(i);
	cmp[B].clear();for(int i:S)cmp[B].pb(i);
}
int con[N][N];
int main(){
	int n;
	scanf("%i %i %i",&n,&p,&q);
	for(int i=1;i<=n;i++){
		int m;scanf("%i",&m);
		while(m--){
			int j;scanf("%i",&j);j++;
			con[i][j]=1;
			E[i].pb(j);
		}
	}
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)if(con[i][j]+con[j][i]==1)return 0*printf("detention\n");
	for(int i=1;i<=n;i++){
		cl();
		in[i]=done[i]=1;a++;
		for(int j:E[i]){
			cns.push(j);
			in_stk[j]=1;
		}
		if(!BCK(i))return 0*printf("detention\n");
		cmp[i].pb(i);
		sort(cmp[i].begin(),cmp[i].end());
	}
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)Fix(i,j);
	int cnt=0;
	for(int i=1;i<=n;i++)if(cmp[i].size())cnt++;
	printf("home\n");
	printf("%i\n",cnt);
	for(int i=1;i<=n;i++)if(cmp[i].size()){
		printf("%i ",cmp[i].size());
		for(int j:cmp[i])printf("%i ",j-1);
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

friends.cpp: In function 'bool BCK(int)':
friends.cpp:11:29: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |  if(a>p||b>q||a+b+cns.size()>p+q)return 0;
      |               ~~~~~~~~~~~~~~^~~~
friends.cpp: In function 'int main()':
friends.cpp:92:12: warning: format '%i' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   92 |   printf("%i ",cmp[i].size());
      |           ~^   ~~~~~~~~~~~~~
      |            |              |
      |            int            std::vector<int>::size_type {aka long unsigned int}
      |           %li
friends.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf("%i %i %i",&n,&p,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
friends.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |   int m;scanf("%i",&m);
      |         ~~~~~^~~~~~~~~
friends.cpp:69:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |    int j;scanf("%i",&j);j++;
      |          ~~~~~^~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 37 / 37
• Subtask 3: 12 / 12
• Subtask 4: 31 / 31