oj.uz

Submission #504044

# Submission time Handle Problem Language Result Execution time Memory
504044 2022-01-09T14:58:14 Z tgbegimx Dynamite (POI11_dyn) C++17
100 / 100
 750 ms 20620 KB 
  #include <iostream>
  #include <cstring>
  #include <algorithm>
  #include <cstdio>
  using namespace std;
  #define N 300005
  int read() {
      int s=0,f=1;
    char ch=getchar();
     for( ; ch<'0'||ch>'9'; f=(ch=='-')?-1:f,ch=getchar()) ;
     for( ; ch>='0'&&ch<='9'; s=s*10+(ch^48),ch=getchar()) ;
     return s*f;
 }
 int n,m,tot,r[N],deep[N],Bomb[N],L,R,Ans,son[N],num;
 struct EDGE{int to,next;} c[N<<1];
 void add(int x,int y) {
     c[++tot]=(EDGE){y,r[x]};
     r[x]=tot;
 }
 int Judge[N],f[N];

 void DFS(int u,int fa,int now) {
     int mx1=-0x5f5f5f5f,mx2=-0x5f5f5f5f;
     if(Bomb[u]) mx1=0;
     for(int i=r[u]; ~i; i=c[i].next) {
         if(c[i].to!=fa) {
            //cout<<c[i].to<<' ';
             DFS(c[i].to,u,now);
             if(Judge[c[i].to]==1) mx1=max(mx1,f[c[i].to]+1);
             if(Judge[c[i].to]==2) mx2=max(mx2,f[c[i].to]-1);
             if(Judge[c[i].to]==-1||num>m) {Judge[u]=-1; return ;}
            }}
     if(mx1>mx2) {
         if(mx1>=now) {
             ++num,Judge[u]=2,f[u]=now;
             if(num>m) Judge[u]=-1;
        } else Judge[u]=1,f[u]=mx1;
     } else Judge[u]=2,f[u]=mx2;
 }
 bool check(int now) {
    num=0;
    DFS(1,1,now);
    //cout<<'\n';
    if(Judge[1]==-1) return false;
     if(Judge[1]==1&&f[1]>=0) ++num;
    return num<=m;
 }
 int main() {
     R=n=read(),m=read();
     memset(r,0xff,sizeof(r));
     for(int x,i=1; i<=n; ++i) Bomb[i]=read();
     for(int x,y,i=1; i<n; ++i) x=read(),y=read(),add(x,y),add(y,x);
     while(L<=R) {
        int mid=(L+R)>>1;
        //cout<<mid<<' ';
       if(check(mid))Ans=mid,R=mid-1;
        else L=mid+1;
     } printf("%d",Ans);
     return 0;
 }

Compilation message

dyn.cpp: In function 'int main()':
dyn.cpp:52:14: warning: unused variable 'x' [-Wunused-variable]
   52 |      for(int x,i=1; i<=n; ++i) Bomb[i]=read();
      |              ^

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 1 ms 1484 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 6 ms 1868 KB Output is correct
2 Correct 14 ms 2124 KB Output is correct
3 Correct 14 ms 2308 KB Output is correct
4 Correct 22 ms 4044 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2868 KB Output is correct
2 Correct 42 ms 3404 KB Output is correct
3 Correct 55 ms 3660 KB Output is correct
4 Correct 62 ms 6584 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 4208 KB Output is correct
2 Correct 61 ms 4172 KB Output is correct
3 Correct 84 ms 4228 KB Output is correct
4 Correct 107 ms 9116 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 7040 KB Output is correct
2 Correct 263 ms 7764 KB Output is correct
3 Correct 524 ms 15684 KB Output is correct
4 Correct 585 ms 15768 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 12188 KB Output is correct
2 Correct 433 ms 9676 KB Output is correct
3 Correct 691 ms 14920 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 18604 KB Output is correct
2 Correct 489 ms 9692 KB Output is correct
3 Correct 750 ms 20620 KB Output is correct
4 Correct 109 ms 9676 KB Output is correct