QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204301#2475. Bank RobberyOIerwanhongWA 2ms3696kbC++142.2kb2023-10-07 09:31:362023-10-07 09:31:37

Judging History

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

  • [2023-10-07 09:31:37]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3696kb
  • [2023-10-07 09:31:36]
  • 提交

answer

#include<bits/stdc++.h>
#define flush() fflush(stdout)
const int MAXN = 111;

std::vector<int>g[MAXN];
int fa[MAXN],sum[MAXN],size[MAXN], leaves[MAXN],dep[MAXN];
int mark[MAXN];
int p,r;
void dfs0(int u)
{
	sum[u]=mark[u],size[u]=1;
	leaves[u]= (g[u].size()==1);
	for(auto v:g[u])
		if(v!=fa[u])
		{
			fa[v]=u,dep[v]=dep[u]+1;
			dfs0(v);
			sum[u]+=sum[v],leaves[u]+=leaves[v];
			size[u]+=size[v];
		}
	if(!mark[u]&&sum[u]<size[u]-leaves[u]+1)
	{
		bool f=g[u].size()>1||u==r;
		bool pr=g[p].size()>1||p==r;
		if((f>pr)||(f==pr&& dep[u]>dep[p]))p=u;
	}
}
void clear(){memset(fa,0,sizeof fa),memset(dep,0,sizeof dep),memset(size,0,sizeof size);p=0;}
int fast(int n)
{
	for(int u=1;u<=n;++u)
		if(!mark[u])
		{
			bool ok=0;
			for(auto v:g[u])
				if(mark[v])ok=1;
			if(!ok)return u;
		}
	return 0;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;++i)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		++u,++v;
		g[u].emplace_back(v),g[v].emplace_back(u);
	}
	int all=0;
	for(int u=1;u<=n;++u)
		if(g[u].size()==1)r=u,++all;
	
	int rm=m-(n-all+1);	
	if(rm>=0)
	{
		puts("DEFEND"),flush();
		for(int u=1;u<=n;++u)
			if(g[u].size()==1)
			{
				if(u==r)mark[u]=1;
				else if(rm)mark[u]=1,--rm;
			}
			else mark[u]=1;
		for(int u=1;u<=n;++u)
			if(mark[u])printf("%d ",u-1);
		puts(""),flush();
		clear(),dfs0(r);
		for(int T=1;T<=365;++T)
		{
			int x;//announce x
			scanf("%d",&x);
			if(x==-1)return 0;
			++x;
			if(mark[x]){puts("0"),flush();continue;}
			//x must be a leaf
			mark[x]=1,mark[r]=0;
			r=x;
			printf("%d ",dep[x]);
			while(fa[x])printf("%d %d ",fa[x]-1,x-1),x=fa[x];
			puts(""),flush();
			clear(),dfs0(r);
		}
	}
	else
	{
		puts("ATTACK"),flush();
		int x;
		for(int w=1;w<=m;++w)scanf("%d",&x),mark[++x]=1;
		clear(),dfs0(r);
		for(int T=1;T<=n;++T)
		{
			int v=fast(n);
			if(v)
			{
				printf("%d\n",v-1),flush();
				return 0;
			}
			printf("%d\n",p-1),flush();
			bool ok=0;
			for(auto v:g[p])
				if(mark[v])ok=1;
			if(!ok)return 0;
			int k;
			scanf("%d",&k);
			while(k--)
			{
				int x,y;
				scanf("%d%d",&x,&y);
				++x,++y;
				--mark[x],++mark[y];
			}
			clear(),dfs0(r);
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3604kb

input:

6 3
0 1
0 2
0 3
3 4
3 5
2
4
5
1
2
5
1
5
1
2
1
2
1
5
4
2
5
1
2
5
4
5
2
1
4
5
2
5
1
2
4
2
4
5
1
2
5
4
5
4
1
5
1
2
5
2
5
1
2
4
5
4
2
1
5
1
2
1
4
5
4
2
5
4
1
2
4
2
4
1
2
5
1
2
4
2
1
5
4
5
2
1
2
4
1
4
5
4
5
2
4
5
4
2
5
2
1
5
4
5
2
4
5
1
5
2
5
2
5
1
4
2
1
4
1
5
4
5
2
4
5
1
5
2
1
2
1
4
1
4
2
1
5
1
4
1
2
5
...

output:

DEFEND
0 3 5 
3 0 2 3 0 5 3 
3 3 4 0 3 2 0 
2 3 5 4 3 
3 0 1 3 0 5 3 
2 0 2 1 0 
3 3 5 0 3 2 0 
3 0 1 3 0 5 3 
3 3 5 0 3 1 0 
3 0 1 3 0 5 3 
2 0 2 1 0 
2 0 1 2 0 
2 0 2 1 0 
2 0 1 2 0 
3 3 5 0 3 1 0 
2 3 4 5 3 
3 0 2 3 0 4 3 
3 3 5 0 3 2 0 
3 0 1 3 0 5 3 
2 0 2 1 0 
3 3 5 0 3 2 0 
2 3 4 5 3 
2 3 5 4...

result:

ok 

Test #2:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

6 2
0 1
0 2
0 3
3 4
3 5
0 3
2 0 3 3 5

output:

ATTACK
5
1

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3696kb

input:

100 50
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
18 38
18 39
19 40
19 41
20 42
20 43
21 44
21 45
22 46
22 47
23 48
23 49
24 50
24 51
25 52
25 53
26 54...

output:

DEFEND
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 99 
11 34 70 16 34 7 16 2 7 0 2 1 0 4 1 10 4 23 10 48 23 99 48 
6 36 74 17 36 7 17 16 7 34 16 70 34 
2 36 75 74 36 
11 46 94 22 46 10 22 4 10 1 4 0 1 2 0 7 ...

result:

ok 

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

100 49
0 1
0 2
0 3
1 4
1 5
2 6
2 7
3 8
3 9
4 10
4 11
5 12
5 13
6 14
6 15
7 16
7 17
8 18
8 19
9 20
9 21
10 22
10 23
11 24
11 25
12 26
12 27
13 28
13 29
14 30
14 31
15 32
15 33
16 34
16 35
17 36
17 37
18 38
18 39
19 40
19 41
20 42
20 43
21 44
21 45
22 46
22 47
23 48
23 49
24 50
24 51
25 52
25 53
26 54...

output:

ATTACK
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0
99
0

result:

wrong answer the contestant was not able to beat me in 100 turns; giving WA