QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#203542 | #2475. Bank Robbery | nameless_story# | RE | 0ms | 0kb | C++20 | 3.7kb | 2023-10-06 17:59:55 | 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