QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203542#2475. Bank Robberynameless_story#RE 0ms0kbC++203.7kb2023-10-06 17:59:552023-10-06 17:59:55

Judging History

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

  • [2023-10-06 17:59:55]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-06 17:59:55]
  • 提交

answer

#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }

const int N=200;
int fa[N],sum[N],non[N],vis[N],dep[N],rt;
int n,m;
vector<int> e[N];
void dfs(int u)
{
	dep[u]=dep[fa[u]]+1;
	for (int v:e[u])
	{
		if (v==fa[u]) continue;
		fa[v]=u;
		dfs(v);
	}
}
int lca(int x,int y)
{
	while (dep[x]>dep[y]) x=fa[x];
	while (dep[y]>dep[x]) y=fa[y];
	while (x!=y) { x=fa[x]; y=fa[y]; }
	return x;
}
int defend()
{
	cout<<"DEFEND\n";
	vector<int> o;
	for (int i=1; i<=n; ++i)
	{
		if (e[i].size()>1) o.push_back(i);
	}
	int y=0;
	for (int i=1; i<=n; ++i)
	{
		if (e[i].size()==1&&o.size()<m)
		{
			o.push_back(i);
			y=i;
		}
	}
	vector<int> vis(n+1);
	for (int i=0; i<o.size(); ++i)
	{
		int x=o[i];
		vis[x]=1;
		cout<<x-1<<" \n"[i+1==o.size()];
	}
	cout.flush();
	while (1)
	{
		int x; cin>>x;
		if (x==-1)
		{
			return 0;
		}
		if (vis[x])
		{
			cout<<0<<'\n';
		}
		else
		{
			assert(vis[y]);
			int z=lca(x,y);
			int num=dep[x]+dep[y]-dep[z]*2;
			cout<<num;
			while (x!=z)
			{
				cout<<' '<<fa[x]-1<<' '<<x-1;
				x=fa[x];
			}
			while (y!=z)
			{
				cout<<' '<<y-1<<' '<<fa[y]-1;
				y=fa[y];
			}
			cout<<'\n';
		}
		cout.flush();
		vis[x]=1; vis[y]=0;
		y=x;
	}
}
void dfs2(int u)
{
	sum[u]=vis[u];
	non[u]=(e[u].size()>1);
	for (int v:e[u])
	{
		if (v==fa[u]) continue;
		dfs2(v);
		sum[u]+=sum[v];
		non[u]+=non[v];
	}
}
void add(int x,int k)
{
	vis[x]+=k;
	while (x)
	{
		sum[x]+=k;
		x=fa[x];
	}
}
void go(int u);
int atk(int u)
{
	if (vis[u]==0)
	{
		go(u);
		return 0;
	}
	if (e[u].size()==1)
	{
		cout<<u<<'\n';
		cout.flush();
		int num; cin>>num;
		while (num--)
		{
			int x,y; cin>>x>>y;
			add(x,-1); add(y,1);
		}
		return 1;
	}
	for (int v:e[u])
	{
		if (v==fa[u]) continue;
		if (sum[v]<non[v])
		{
			go(v);
			return 0;
		}
	}
	for (int v:e[u])
	{
		if (v==fa[u]) continue;
		assert(sum[v]==non[v]);
		return atk(v);
	}
	assert(0);
	return -1;
}
void go(int u)
{
	if (sum[u]==non[u])
	{
		if (vis[u]==0)
		{
			for (int v:e[u])
			{
				if (v==fa[u]) continue;
				if (sum[v]==non[v])
				{
					go(v);
					return;
				}
			}
		}
		else
		{
			for (int v:e[u])
			{
				if (v==fa[u]) continue;
				if (sum[v]<non[v])
				{
					go(v);
					return;
				}
			}
			for (int v:e[u])
			{
				if (v==fa[u]) continue;
				atk(v);
				if (vis[u]==1)
				{
					go(v);
					return;
				}
				else
				{
					for (int w:e[u])
					{
						if (w==fa[u]) continue;
						if (w!=v)
						{
							go(w);
							return;
						}
					}
				}
			}
		}
	}
	assert(sum[u]<non[u]);
	if (vis[u]==1)
	{
		for (int v:e[u])
		{
			if (v==fa[u]) continue;
			if (sum[v]<non[v])
			{
				go(v);
				return;
			}
		}
		assert(0);
	}
	else
	{
		for (int v:e[u])
		{
			if (v==fa[u]) continue;
			if (sum[v]<non[v])
			{
				go(v);
				return;
			}
		}
		for (int v:e[u])
		{
			if (v==fa[u]) continue;
			assert(sum[v]==non[v]);
			go(v);
			return;
		}
	}
}
void attack()
{
	cout<<"ATTACK\n";
	cout.flush();
	for (int i=1; i<=m; ++i)
	{
		int x; cin>>x;
		vis[x]=1;
	}
	dfs2(rt);
	go(rt);
}
int main()
{
	cin>>n>>m;
	for (int i=1; i<n; ++i)
	{
		int x,y; cin>>x>>y;
		++x; ++y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	int cnt=0;
	for (int i=1; i<=n; ++i)
	{
		if (e[i].size()>1) rt=i;
		else ++cnt;
	}
	dfs(rt);
	if (m<=n-cnt)
	{
		attack();
	}
	else
	{
		defend();
	}
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

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

output:

DEFEND
0 3 1
0

result: