oj.uz

Submission #505087

# Submission time Handle Problem Language Result Execution time Memory
505087 2022-01-10T13:12:10 Z tgbegimx Dynamite (POI11_dyn) C++17
100 / 100
 900 ms 20612 KB 
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 1000000000
#define maxn 300005
using namespace std;
int n,m;
int a[maxn];
int ans;
struct edge
{
int to,ne;
}b[maxn*2];
int k=0,head[maxn];
int f[maxn],g[maxn];
int limit;
int num=0,op1=0;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return x*f;
}
void add(int u,int v)
{
k++;
b[k].to=v; b[k].ne=head[u]; head[u]=k;
}
void dfs(int x,int pre)
{
f[x]=INF; //The closest distance from the detonated point in the subtree rooted at i to i
if(a[x])
g[x]=0; //The farthest distance between the unexploded point in the subtree rooted at i and i
else
g[x]=-INF;
for(int i=head[x];i!=-1;i=b[i].ne)
if(b[i].to!=pre)
{
dfs(b[i].to,x);
f[x]=min(f[x],f[b[i].to]+1);//Find a tipping point closest to x
g[x]=max(g[x],g[b[i].to]+1);//An unexploded point farthest from x
}
if(g[x]+f[x]<=limit)
//For the subtree rooted at x, there is a tipping point that can detonate those unintended points within a specified time
g[x]=-INF;
if(g[x]==limit)
//The distance from the point farthest from x that failed to be detonated from x = limit, indicating that point x must be ignited
{
f[x]=0,g[x]=-INF,num++;
}
}
bool check(int x)
{
if(!x) return op1<=m;
limit=x; num=0;
dfs(1,0);
if(g[1]+f[1]>limit)
num++;
return num<=m;
}
void getans()
{
int l=0,r=n,mid;
ans=n;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
}
int main()
{
memset(head,-1,sizeof(head));
n=read(); m=read();
for(int i=1;i<=n;i++)
{
a[i]=read();
if(a[i]) op1++;
}
int x,y;
for(int i=1;i<n;i++)
{
x=read(); y=read();
add(x,y); add(y,x);
}
getans();
printf("%d\n",ans);
return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 2 ms 1480 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1740 KB Output is correct
2 Correct 13 ms 2132 KB Output is correct
3 Correct 17 ms 2304 KB Output is correct
4 Correct 22 ms 3916 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2852 KB Output is correct
2 Correct 51 ms 3396 KB Output is correct
3 Correct 85 ms 3660 KB Output is correct
4 Correct 66 ms 6484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 4152 KB Output is correct
2 Correct 78 ms 4204 KB Output is correct
3 Correct 89 ms 4172 KB Output is correct
4 Correct 121 ms 9124 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 7092 KB Output is correct
2 Correct 307 ms 7756 KB Output is correct
3 Correct 654 ms 15716 KB Output is correct
4 Correct 590 ms 15660 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 800 ms 12144 KB Output is correct
2 Correct 643 ms 9676 KB Output is correct
3 Correct 756 ms 14788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 18600 KB Output is correct
2 Correct 677 ms 9652 KB Output is correct
3 Correct 900 ms 20612 KB Output is correct
4 Correct 133 ms 9664 KB Output is correct