QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#546099#34. Friendsgoj_bot1100 ✓126ms10028kbC++142.9kb2024-09-03 19:47:542024-09-03 19:47:54

Judging History

你现在查看的是最新测评结果

  • [2024-09-03 19:47:54]
  • 评测
  • 测评结果:100
  • 用时:126ms
  • 内存:10028kb
  • [2024-09-03 19:47:54]
  • 提交

answer

// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 3000005
#define inf 0x3f3f3f3f

int n,p,q;
bool e[2505][2505];
vi g[2505];

int col[2505],cnt;
vi vec[2505];

int check(vi o){
	if(o.size()>p)return p+q+1;
	int sum=0;
	for(int u:o)sum+=g[u].size();
	for(int u:o)for(int v:o)sum-=e[u][v];
	return sum;
}
bool orz[2505];
vi outs(vi a,vi b){
	vi c;
	for(auto x:b)orz[x]=1;
	for(auto x:a)if(!orz[x])c.pb(x);
	for(auto x:b)orz[x]=0;
	return c;
}
bool in(vi &a,vi &b){
	bool hav=1;
	for(auto x:b)orz[x]=1;
	for(auto x:a)if(!orz[x])hav=0;
	for(auto x:b)orz[x]=0;
	return hav;
}

mt19937_64 rnd(19890531);
vi ans;
map<vi,bool>mp;
bool dfs(vi o){
//	cout<<"dfs: ";for(auto x:o)cout<<x<<" ";puts("");
	if(o.size()>p)return 0;
	int qwq=check(o);
	if(qwq<=q){
		ans=o;
		return 1;
	}
	if(n>1500&&qwq>p+q)return 0;
	
	sort(o.begin(),o.end());
	if(mp.count(o))return 0;
	
	set<int>pos;
	for(auto x:o)for(auto y:g[x])pos.insert(y);
	for(auto x:o)pos.erase(x);
	if(pos.size()+o.size()>p+q)return 0;
	
//	for(auto t:o)cout<<t<<" ";puts("");
	vi vc;
	for(auto x:pos)vc.pb(x);
	shuffle(vc.begin(),vc.end(),rnd);
	int siz=vc.size();
//	cout<<"siz: ";for(int x:vc)cout<<x<<" ";puts(""); 
	For(i,1,(1<<siz)-1)
		if(__builtin_popcount(i)+o.size()<=p){
			vi oo=o;
			For(j,0,siz-1)if(i>>j&1)oo.pb(vc[j]);
			if(dfs(oo))return 1;
		}
	mp[o]=1;
	return 0;
}

signed main()
{
//	freopen("test31_true.in","r",stdin);
	n=read(),p=read(),q=read();
	For(i,0,n-1){
		g[i].resize(read());
		for(auto&x:g[i])x=read(),e[i][x]=1;
	}
	For(i,0,n-1)For(j,0,n-1)if(e[i][j]&&!e[j][i])puts("detention"),exit(0);
	For(i,0,n-1)if(g[i].size()>p+q)puts("detention"),exit(0); 
	For(i,0,n-1){
		if(col[i])continue;
	//	int m=g[i].size();
		mp.clear();
		vi o={i}; ans.clear();
		if(!dfs(o)){
			puts("detention");
			exit(0); 
		}
		vec[i]=ans;
		for(auto x:vec[i])col[x]=1;
	}
	For(i,0,n)col[i]=0;
	For(i,0,n-1)
		For(j,i+1,n-1){
			if(in(vec[i],vec[j])){vec[i].clear();continue;}
			if(in(vec[j],vec[i])){vec[j].clear();continue;}
			vi o1=outs(vec[i],vec[j]);
			if(check(o1)<=q){vec[i]=o1;continue;}
			vi o2=outs(vec[j],vec[i]);
			if(check(o2)<=q){vec[j]=o2;continue;}
			assert(0);
		}
	puts("home");
	vector<vi>res; 
	For(i,0,n-1)
		if(!col[i] && vec[i].size()){
			for(auto u:vec[i]) col[u]=1;
			res.pb(vec[i]);
		}
	cout<<res.size()<<"\n";
	for(auto t:res){
		cout<<t.size()<<" ";
		for(int x:t)cout<<x<<" ";
		puts("");
	}
	return 0;
}

详细

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 1ms
memory: 3720kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #2:

score: 20
Accepted
time: 1ms
memory: 3788kb

input:

5 1 2
2 1 4
2 0 2
2 1 4
0
2 0 2

output:

home
5
1 0 
1 1 
1 2 
1 3 
1 4 

result:

ok correct plan!

Test #3:

score: 20
Accepted
time: 0ms
memory: 3760kb

input:

10 2 2
2 1 5
2 0 2
2 1 3
2 2 4
1 3
1 0
1 7
1 6
1 9
1 8

output:

home
10
1 0 
1 1 
1 2 
1 3 
1 4 
1 5 
1 6 
1 7 
1 8 
1 9 

result:

ok correct plan!

Test #4:

score: 20
Accepted
time: 0ms
memory: 3656kb

input:

15 2 3
3 1 2 3
2 0 2
3 0 1 3
3 0 2 4
4 3 5 6 8
1 4
2 4 7
3 6 8 9
3 4 7 9
2 7 8
2 11 13
3 10 12 13
2 11 13
3 10 11 12
0

output:

home
14
1 0 
1 1 
1 2 
1 3 
2 4 5 
1 6 
1 7 
1 8 
1 9 
1 10 
1 11 
1 12 
1 13 
1 14 

result:

ok correct plan!

Test #5:

score: 20
Accepted
time: 1ms
memory: 3784kb

input:

16 3 3
2 1 2
3 0 2 7
4 0 1 6 9
2 4 14
3 3 12 13
2 6 7
3 2 5 7
3 1 5 6
0
2 2 14
2 11 12
2 10 12
3 4 10 11
3 4 14 15
4 3 9 13 15
2 13 14

output:

home
12
3 1 2 0 
1 3 
1 4 
1 5 
1 6 
1 7 
1 8 
1 9 
1 10 
1 11 
1 12 
3 14 15 13 

result:

ok correct plan!

Test #6:

score: 20
Accepted
time: 1ms
memory: 3788kb

input:

16 4 4
3 1 2 3
3 0 2 3
6 0 1 3 5 6 9
4 0 1 2 11
4 5 6 7 15
5 2 4 6 7 15
4 2 4 5 7
3 4 5 6
3 9 10 11
5 2 8 10 11 14
5 8 9 11 12 13
4 3 8 9 10
4 10 13 14 15
4 10 12 14 15
4 9 12 13 15
5 4 5 12 13 14

output:

detention

result:

ok no solution

Test #7:

score: 20
Accepted
time: 0ms
memory: 3756kb

input:

16 3 3
3 1 3 6
3 0 2 3
2 1 3
4 0 1 2 12
2 5 6
4 4 6 13 14
4 0 4 5 13
3 8 9 15
2 7 9
2 7 8
2 11 12
2 10 12
3 3 10 11
4 5 6 14 15
3 5 13 15
3 7 13 14

output:

detention

result:

ok no solution

Test #8:

score: 20
Accepted
time: 0ms
memory: 3772kb

input:

16 5 5
3 1 2 4
1 0
2 0 3
4 2 4 5 13
3 0 1 3
5 3 6 7 8 9
3 5 7 9
6 5 6 8 9 12 14
4 5 7 9 14
4 5 6 7 8
4 11 12 13 14
4 10 12 13 14
5 7 10 11 13 14
4 3 10 11 12
5 7 8 10 11 12
0

output:

detention

result:

ok no solution

Subtask #2:

score: 37
Accepted

Test #9:

score: 37
Accepted
time: 1ms
memory: 3936kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #10:

score: 37
Accepted
time: 1ms
memory: 4240kb

input:

200 8 2
5 1 4 5 6 7
6 0 2 3 5 6 10
5 1 3 5 6 7
5 1 2 4 6 7
3 0 3 6
4 0 1 2 6
7 0 1 2 3 4 5 7
5 0 2 3 6 10
6 9 10 11 12 13 14
7 8 10 11 12 13 14 15
8 1 7 8 9 11 12 13 14
7 8 9 10 12 13 14 15
4 8 9 10 11
5 8 9 10 11 15
5 8 9 10 11 15
4 9 11 13 14
8 17 18 19 20 21 22 23 35
7 16 18 19 20 21 22 23
6 16 1...

output:

home
26
8 0 2 3 4 5 6 7 1 
8 8 9 10 11 12 13 14 15 
8 16 17 19 20 21 22 23 18 
8 24 25 26 28 29 30 31 27 
8 32 33 34 35 36 37 39 38 
8 40 41 43 44 45 46 47 42 
8 48 49 50 51 53 54 55 52 
7 56 57 59 60 61 62 58 
8 63 64 65 67 68 69 70 66 
8 71 72 73 74 75 76 78 77 
8 79 81 82 83 84 85 86 80 
8 87 88 ...

result:

ok correct plan!

Test #11:

score: 37
Accepted
time: 1ms
memory: 4056kb

input:

150 5 2
2 1 2
4 0 2 3 6
2 0 1
5 1 4 5 6 7
4 3 5 6 7
4 3 4 6 7
5 1 3 4 5 7
4 3 4 5 6
4 9 10 12 17
5 8 10 11 12 13
3 8 9 12
2 9 12
4 8 9 10 11
4 9 14 15 16
4 13 15 16 17
4 13 14 16 17
4 13 14 15 17
4 8 14 15 16
4 19 20 21 22
5 18 20 21 22 46
4 18 19 21 22
5 18 19 20 22 31
4 18 19 20 21
4 24 25 26 27
3...

output:

home
37
3 1 2 0 
5 3 4 6 7 5 
5 8 10 11 12 9 
5 13 14 15 17 16 
5 18 19 20 21 22 
5 23 24 25 26 27 
1 28 
2 29 30 
5 31 33 34 35 32 
5 36 37 38 40 39 
4 41 42 43 44 
5 45 46 47 48 49 
5 50 52 53 54 51 
3 55 57 56 
5 58 59 61 62 60 
1 63 
1 64 
5 65 66 68 69 67 
5 70 72 73 74 71 
5 75 77 78 79 76 
5 ...

result:

ok correct plan!

Test #12:

score: 37
Accepted
time: 0ms
memory: 6440kb

input:

250 6 2
5 1 2 3 4 5
3 0 3 4
5 0 3 4 5 17
4 0 1 2 5
4 0 1 2 5
5 0 2 3 4 12
4 7 9 10 11
6 6 8 9 10 11 46
4 7 9 10 11
6 6 7 8 10 11 43
5 6 7 8 9 11
5 6 7 8 9 10
6 5 13 14 15 16 17
5 12 14 15 16 17
4 12 13 15 16
4 12 13 14 17
4 12 13 14 17
5 2 12 13 15 16
5 19 20 21 22 23
5 18 20 21 22 23
5 18 19 21 22 ...

output:

detention

result:

ok no solution

Test #13:

score: 37
Accepted
time: 2ms
memory: 4312kb

input:

250 7 2
6 1 2 3 4 5 6
6 0 2 3 4 5 6
7 0 1 3 4 5 6 7
6 0 1 2 4 5 6
6 0 1 2 3 5 6
6 0 1 2 3 4 6
7 0 1 2 3 4 5 8
2 2 8
2 6 7
4 10 11 12 17
3 9 11 12
4 9 10 12 19
3 9 10 11
5 14 15 17 18 19
6 13 15 16 17 18 19
6 13 14 16 17 18 19
5 14 15 17 18 19
7 9 13 14 15 16 18 19
6 13 14 15 16 17 19
7 11 13 14 15 1...

output:

detention

result:

ok no solution

Test #14:

score: 37
Accepted
time: 1ms
memory: 6272kb

input:

250 5 2
3 1 3 7
3 0 2 3
3 1 3 4
3 0 1 2
1 2
3 6 7 8
5 1 5 7 8 9
4 0 5 6 8
4 5 6 7 9
2 6 8
2 14 25
3 12 13 14
2 11 14
2 11 44
3 10 11 12
5 16 17 18 19 20
3 15 18 19
3 15 18 19
4 15 16 17 28
3 15 16 17
5 15 21 22 23 24
4 20 22 23 24
5 20 21 23 24 36
4 20 21 22 24
4 20 21 22 23
5 10 26 27 28 29
4 25 27...

output:

detention

result:

ok no solution

Test #15:

score: 37
Accepted
time: 1ms
memory: 3960kb

input:

100 5 0
4 1 2 3 4
4 0 2 3 4
3 0 1 4
3 0 1 4
4 0 1 2 3
3 6 7 8
4 5 7 8 9
4 5 6 8 9
4 5 6 7 9
3 6 7 8
3 11 12 14
3 10 12 14
4 10 11 13 14
2 12 14
4 10 11 12 13
2 16 17
2 15 17
2 15 16
4 19 20 21 22
4 18 20 21 22
3 18 19 21
4 18 19 20 22
3 18 19 21
4 24 25 26 27
3 23 26 27
3 23 26 27
4 23 24 25 27
4 23...

output:

home
24
5 0 2 3 4 1 
5 5 7 8 9 6 
5 10 11 13 14 12 
3 15 16 17 
5 18 19 20 21 22 
5 23 24 26 27 25 
5 28 29 30 32 31 
5 33 34 35 37 36 
5 38 39 40 42 41 
5 43 44 45 46 47 
5 48 49 50 51 52 
5 53 54 55 56 57 
5 58 59 61 62 60 
4 63 65 66 64 
2 67 68 
2 69 70 
5 71 72 73 75 74 
5 76 77 79 80 78 
5 81 ...

result:

ok correct plan!

Test #16:

score: 37
Accepted
time: 1ms
memory: 4248kb

input:

250 10 1
9 1 2 3 4 5 6 7 8 9
9 0 2 3 4 5 6 7 8 9
9 0 1 3 4 5 6 7 8 9
9 0 1 2 4 5 6 7 8 9
9 0 1 2 3 5 6 7 8 9
9 0 1 2 3 4 6 7 8 9
9 0 1 2 3 4 5 7 8 9
9 0 1 2 3 4 5 6 8 9
9 0 1 2 3 4 5 6 7 9
10 0 1 2 3 4 5 6 7 8 12
9 11 12 13 14 15 16 17 18 19
9 10 12 13 14 15 16 17 18 19
10 9 10 11 13 14 15 16 17 18 ...

output:

home
28
10 0 1 2 3 4 5 6 8 9 7 
10 10 11 12 13 14 15 17 18 19 16 
10 20 21 22 23 25 26 27 28 29 24 
10 30 31 32 33 34 35 37 38 39 36 
9 40 41 42 43 44 45 47 48 46 
10 49 51 52 53 54 55 56 57 58 50 
10 59 60 61 62 63 64 65 66 67 68 
10 69 70 71 72 73 74 76 77 78 75 
10 79 81 82 83 84 85 86 87 88 80 
...

result:

ok correct plan!

Subtask #3:

score: 12
Accepted

Dependency #2:

100%
Accepted

Test #17:

score: 12
Accepted
time: 0ms
memory: 3628kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #18:

score: 12
Accepted
time: 7ms
memory: 7652kb

input:

1000 10 0
6 1 2 3 5 6 7
7 0 2 3 4 5 6 7
7 0 1 3 4 5 6 7
7 0 1 2 4 5 6 7
6 1 2 3 5 6 7
7 0 1 2 3 4 6 7
7 0 1 2 3 4 5 7
7 0 1 2 3 4 5 6
9 9 10 11 12 13 14 15 16 17
8 8 10 12 13 14 15 16 17
8 8 9 11 12 13 14 15 17
8 8 10 12 13 14 15 16 17
9 8 9 10 11 13 14 15 16 17
8 8 9 10 11 12 15 16 17
7 8 9 10 11 1...

output:

home
111
8 0 1 3 4 5 6 7 2 
10 8 9 10 11 13 14 15 16 17 12 
10 18 19 20 21 22 23 24 26 27 25 
10 28 29 30 32 33 34 35 36 37 31 
10 38 39 41 42 43 44 45 46 47 40 
10 48 49 50 51 52 53 54 55 56 57 
4 58 59 60 61 
9 62 63 64 66 67 68 69 70 65 
2 71 72 
10 73 74 75 76 77 78 79 80 81 82 
10 83 84 86 87 8...

result:

ok correct plan!

Test #19:

score: 12
Accepted
time: 11ms
memory: 6852kb

input:

1250 8 1
7 1 2 3 4 5 6 7
7 0 2 3 4 5 6 7
7 0 1 3 4 5 6 7
7 0 1 2 4 5 6 7
8 0 1 2 3 5 6 7 23
7 0 1 2 3 4 6 7
7 0 1 2 3 4 5 7
7 0 1 2 3 4 5 6
7 9 10 11 12 13 14 15
7 8 10 11 12 13 14 15
7 8 9 11 12 13 14 15
8 8 9 10 12 13 14 15 51
7 8 9 10 11 13 14 15
7 8 9 10 11 12 14 15
7 8 9 10 11 12 13 15
7 8 9 10...

output:

home
176
8 0 2 3 4 5 6 7 1 
8 8 9 10 11 12 14 15 13 
8 16 17 19 20 21 22 23 18 
8 24 25 26 27 29 30 31 28 
8 32 33 34 35 36 37 38 39 
8 40 41 42 44 45 46 47 43 
8 48 49 51 52 53 54 55 50 
8 56 57 59 60 61 62 63 58 
1 64 
8 65 66 67 68 69 71 72 70 
8 73 75 76 77 78 79 80 74 
8 81 82 83 84 85 87 88 86...

result:

ok correct plan!

Test #20:

score: 12
Accepted
time: 23ms
memory: 8228kb

input:

1200 9 2
7 1 2 3 4 5 7 8
7 0 3 4 5 6 7 8
8 0 3 4 5 6 7 8 29
6 0 1 2 4 7 8
8 0 1 2 3 5 6 7 8
6 0 1 2 4 7 8
3 1 2 4
8 0 1 2 3 4 5 8 10
7 0 1 2 3 4 5 7
8 10 11 12 13 14 15 16 17
9 7 9 11 12 13 14 15 16 17
8 9 10 12 13 14 15 16 17
7 9 10 11 13 16 17 27
8 9 10 11 12 14 15 16 17
7 9 10 11 13 15 16 17
7 9 ...

output:

home
157
9 0 1 2 3 5 6 7 8 4 
9 9 10 11 12 13 14 15 16 17 
8 18 19 20 21 23 24 25 22 
9 26 28 29 30 31 32 33 34 27 
1 35 
7 36 37 39 40 41 42 38 
9 43 44 45 46 47 48 50 51 49 
9 52 54 55 56 57 58 59 60 53 
9 61 62 63 64 65 66 67 68 69 
9 70 71 72 74 75 76 77 78 73 
9 79 80 81 82 83 84 85 87 86 
9 88...

result:

ok correct plan!

Test #21:

score: 12
Accepted
time: 17ms
memory: 7088kb

input:

1250 9 2
6 1 3 4 5 6 8
7 0 2 3 4 5 6 20
4 1 3 5 6
6 0 1 2 4 5 6
5 0 1 3 5 6
6 0 1 2 3 4 6
6 0 1 2 3 4 5
7 8 9 10 12 13 14 15
8 0 7 9 10 11 12 14 15
8 7 8 10 11 12 13 14 15
8 7 8 9 11 12 13 14 15
6 8 9 10 12 14 15
8 7 8 9 10 11 14 15 38
5 7 9 10 14 15
8 7 8 9 10 11 12 13 15
8 7 8 9 10 11 12 13 14
7 1...

output:

home
165
7 0 1 3 4 5 6 2 
9 7 8 9 11 12 13 14 15 10 
9 16 17 18 20 21 22 23 24 19 
9 25 26 27 28 29 30 31 33 32 
9 34 36 37 38 39 40 41 42 35 
9 43 44 45 46 47 49 50 51 48 
7 52 53 54 55 57 58 56 
9 59 61 62 63 64 65 66 67 60 
9 68 69 70 71 72 73 74 76 75 
9 77 78 80 81 82 83 84 85 79 
9 86 87 88 90...

result:

ok correct plan!

Test #22:

score: 12
Accepted
time: 0ms
memory: 8596kb

input:

1800 6 2
5 1 2 3 4 5
6 0 2 3 4 5 14
5 0 1 3 4 5
5 0 1 2 4 5
6 0 1 2 3 5 26
6 0 1 2 3 4 307
6 7 8 9 10 11 12
5 6 8 9 10 11
4 6 7 9 11
4 6 7 8 10
5 6 7 9 11 13
4 6 7 8 10
2 6 13
2 10 12
5 1 15 16 17 35
3 14 16 17
3 14 15 17
3 14 15 16
4 19 20 21 22
4 18 20 21 22
4 18 19 21 22
6 18 19 20 22 32 40
4 18 ...

output:

detention

result:

ok no solution

Test #23:

score: 12
Accepted
time: 5ms
memory: 9912kb

input:

1800 7 2
6 1 2 3 4 5 6
9 0 2 3 4 5 6 13 19 484
6 0 1 3 4 5 6
6 0 1 2 4 5 6
6 0 1 2 3 5 6
6 0 1 2 3 4 6
6 0 1 2 3 4 5
6 8 9 10 11 12 13
6 7 9 10 12 13 24
4 7 8 10 13
5 7 8 9 11 13
3 7 10 12
3 7 8 11
5 1 7 8 9 10
5 15 16 17 18 19
6 14 16 17 18 19 20
5 14 15 17 18 19
4 14 15 16 18
6 14 15 16 17 19 20
5...

output:

detention

result:

ok no solution

Test #24:

score: 12
Accepted
time: 2ms
memory: 9336kb

input:

2000 5 2
3 2 3 4
2 2 3
4 0 1 3 4
5 0 1 2 4 9
5 0 1 2 3 10
2 6 9
4 5 7 8 9
3 6 8 9
3 6 7 9
6 3 5 6 7 8 11
5 4 11 12 13 14
5 9 10 12 13 14
3 10 11 13
4 10 11 12 14
3 10 11 13
4 16 17 18 19
5 15 17 18 19 34
5 15 16 18 19 24
4 15 16 17 19
4 15 16 17 18
4 21 22 23 24
5 20 22 23 24 33
4 20 21 23 24
4 20 2...

output:

detention

result:

ok no solution

Subtask #4:

score: 31
Accepted

Test #25:

score: 31
Accepted
time: 0ms
memory: 3904kb

input:

2 2 2
1 1
0

output:

detention

result:

ok no solution

Test #26:

score: 31
Accepted
time: 57ms
memory: 9096kb

input:

1900 6 5
5 2 3 4 5 6
4 2 4 5 7
5 0 1 3 4 5
6 0 2 4 5 6 11
5 0 1 2 3 6
4 0 1 2 3
8 0 3 4 7 8 9 10 11
5 1 6 8 9 11
5 6 7 9 10 11
4 6 7 8 11
3 6 8 11
6 3 6 7 8 9 10
5 13 15 16 17 29
6 12 14 15 16 17 37
4 13 15 16 17
5 12 13 14 16 17
6 12 13 14 15 17 37
7 12 13 14 15 16 24 32
5 19 20 21 22 28
6 18 20 21...

output:

home
592
6 0 1 2 3 5 4 
6 6 7 9 10 11 8 
6 12 13 14 15 16 17 
6 18 19 21 22 23 20 
6 24 26 27 28 29 25 
6 30 31 32 34 35 33 
6 36 37 39 40 41 38 
5 42 43 45 46 44 
1 47 
1 48 
1 49 
1 50 
1 51 
1 52 
1 53 
6 54 55 56 57 59 58 
1 60 
1 61 
6 62 63 64 65 67 66 
6 69 70 71 72 73 68 
6 74 75 76 77 78 79...

result:

ok correct plan!

Test #27:

score: 31
Accepted
time: 51ms
memory: 8628kb

input:

1800 5 5
4 1 2 6 10
5 0 2 4 9 13
2 0 1
3 4 5 23
4 1 3 7 25
5 3 6 7 8 9
5 0 5 7 8 9
6 4 5 6 8 9 14
4 5 6 7 9
5 1 5 6 7 8
5 0 11 12 13 14
4 10 12 13 14
4 10 11 13 14
7 1 10 11 12 14 17 31
5 7 10 11 12 13
6 16 19 21 24 29 33
1 15
5 13 18 19 20 21
6 17 19 20 21 24 26
5 15 17 18 20 21
4 17 18 19 21
5 15 ...

output:

home
564
1 0 
1 1 
1 2 
1 3 
1 4 
5 6 7 8 9 5 
5 10 11 12 13 14 
2 15 16 
5 17 18 19 20 21 
5 23 24 25 26 22 
5 28 29 30 31 27 
5 33 34 35 36 32 
5 38 39 40 41 37 
1 42 
1 43 
5 44 45 46 47 48 
5 50 51 52 53 49 
5 54 55 56 57 58 
5 59 60 62 63 61 
5 65 66 67 68 64 
5 69 71 72 73 70 
1 74 
1 75 
1 76...

result:

ok correct plan!

Test #28:

score: 31
Accepted
time: 29ms
memory: 9688kb

input:

1650 6 5
5 1 3 4 5 7
6 0 2 3 4 5 25
4 1 3 4 5
7 0 1 2 4 5 12 28
6 0 1 2 3 5 13
5 0 1 2 3 4
4 7 8 10 11
6 0 6 8 9 10 11
6 6 7 9 10 11 53
4 7 8 10 11
7 6 7 8 9 11 34 52
6 6 7 8 9 10 55
4 3 13 20 22
3 4 12 14
6 13 15 16 17 18 19
7 14 16 17 18 19 26 36
5 14 15 17 18 19
7 14 15 16 18 19 34 46
5 14 15 16 ...

output:

home
402
6 1 2 3 4 5 0 
6 6 7 8 10 11 9 
1 12 
1 13 
6 14 16 17 18 19 15 
6 20 21 23 24 25 22 
6 26 27 28 29 30 31 
6 32 33 34 35 37 36 
1 38 
6 39 40 41 42 44 43 
6 45 46 48 49 50 47 
6 51 52 53 54 56 55 
6 57 58 59 60 62 61 
6 63 64 65 67 68 66 
6 69 70 72 73 74 71 
6 75 76 77 79 80 78 
6 81 82 83...

result:

ok correct plan!

Test #29:

score: 31
Accepted
time: 126ms
memory: 7832kb

input:

1050 10 5
3 1 9 10
5 0 3 8 22 270
6 4 5 7 9 10 11
7 1 4 5 6 9 10 11
9 2 3 5 6 7 8 9 10 11
7 2 3 4 6 9 10 11
7 3 4 5 7 8 9 10
7 2 4 6 8 9 10 11
6 1 4 6 7 10 11
9 0 2 3 4 5 6 7 10 11
9 0 2 3 4 5 6 7 8 9
8 2 3 4 5 7 8 9 22
9 13 14 15 16 17 18 19 20 21
10 12 14 15 16 17 18 19 20 21 37
10 12 13 15 16 18 ...

output:

detention

result:

ok no solution

Test #30:

score: 31
Accepted
time: 84ms
memory: 8556kb

input:

1300 7 7
7 2 3 4 5 6 9 32
5 2 3 4 5 6
8 0 1 3 4 5 6 9 12
7 0 1 2 4 5 10 11
6 0 1 2 3 5 6
6 0 1 2 3 4 6
6 0 1 2 4 5 9
5 8 9 11 12 13
5 7 9 10 11 13
9 0 2 6 7 8 10 11 12 13
6 3 8 9 11 12 13
8 3 7 8 9 10 12 13 31
6 2 7 9 10 11 13
6 7 8 9 10 11 12
8 15 16 17 18 19 20 24 32
6 14 16 17 18 19 20
7 14 15 17...

output:

detention

result:

ok no solution

Test #31:

score: 31
Accepted
time: 27ms
memory: 8112kb

input:

1300 9 4
5 2 3 4 6 7
6 3 4 5 6 7 13
7 0 3 4 5 6 7 8
6 0 1 2 4 5 8
8 0 1 2 3 5 6 7 8
8 1 2 3 4 6 7 8 16
8 0 1 2 4 5 7 8 14
8 0 1 2 4 5 6 8 12
6 2 3 4 5 6 7
7 10 11 12 13 14 15 16
6 9 12 13 14 15 16
7 9 12 13 14 15 16 17
9 7 9 10 11 13 14 15 16 17
9 1 9 10 11 12 14 15 16 17
9 6 9 10 11 12 13 15 16 17
...

output:

detention

result:

ok no solution

Test #32:

score: 31
Accepted
time: 0ms
memory: 8668kb

input:

2000 5 5
5 1 2 3 4 8
4 0 2 3 4
4 0 1 3 4
7 0 1 2 4 10 12 16
4 0 1 2 3
4 6 7 8 9
5 5 8 9 17 29
3 5 8 9
6 0 5 6 7 9 14
5 5 6 7 8 19
5 3 11 12 13 15
3 10 13 18
3 3 10 13
4 1 10 11 12
5 8 15 16 17 18
5 10 14 16 17 18
5 3 14 15 17 18
5 6 14 15 16 18
5 11 14 15 16 17
6 9 20 21 22 23 24
4 19 21 22 23
5 19 ...

output:

detention

result:

ok no solution

Test #33:

score: 31
Accepted
time: 87ms
memory: 10028kb

input:

2500 9 6
6 1 2 3 4 6 7
5 0 2 3 6 7
6 0 1 4 5 6 7
7 0 1 4 7 8 31 35
6 0 2 3 5 6 8
5 2 4 6 7 8
6 0 1 2 4 5 7
8 0 1 2 3 5 6 15 36
5 3 4 5 19 39
7 10 11 13 14 15 16 39
8 9 11 12 13 14 15 16 40
7 9 10 12 13 14 15 16
9 10 11 13 14 15 16 17 22 33
7 9 10 11 12 14 15 17
8 9 10 11 12 13 15 16 17
9 7 9 10 11 1...

output:

home
419
9 1 2 3 4 5 6 7 8 0 
9 9 10 11 12 13 14 15 16 17 
9 18 19 20 21 22 24 25 26 23 
9 27 28 29 30 31 32 33 34 35 
6 36 38 39 40 41 37 
9 42 44 45 46 47 48 49 50 43 
1 51 
1 52 
1 53 
9 54 55 56 57 58 59 61 62 60 
1 63 
1 64 
1 65 
1 66 
9 67 68 69 71 72 73 74 75 70 
9 76 77 78 79 80 82 83 84 81...

result:

ok correct plan!

Test #34:

score: 31
Accepted
time: 8ms
memory: 9980kb

input:

2500 9 6
8 1 2 3 5 7 8 12 16
9 0 2 3 4 5 6 7 8 14
9 0 1 3 4 5 6 7 8 19
8 0 1 2 4 6 7 8 17
8 1 2 3 5 6 7 8 13
7 0 1 2 4 6 7 8
7 1 2 3 4 5 7 8
7 0 1 2 3 4 5 6
7 0 1 2 3 4 5 6
6 10 12 13 15 16 17
7 9 12 13 14 15 16 17
4 13 14 16 17
7 0 9 10 13 14 15 17
8 4 9 10 11 12 15 16 17
7 1 10 11 12 15 16 17
7 9 ...

output:

detention

result:

ok no solution