QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#204301 | #2475. Bank Robbery | OIerwanhong | WA | 2ms | 3696kb | C++14 | 2.2kb | 2023-10-07 09:31:36 | 2023-10-07 09:31:37 |
Judging History
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