# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
289112 | TadijaSebez | Friends (BOI17_friends) | C++11 | 1088 ms | 11000 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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){
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);
}
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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |