oj.uz

Submission #504043

# Submission time Handle Problem Language Result Execution time Memory
504043 2022-01-09T14:57:08 Z tgbegimx Dynamite (POI11_dyn) C++17
0 / 100
 1464 ms 56396 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
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 Incorrect 1 ms 1484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 2380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 6868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 13192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 699 ms 29960 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1370 ms 50400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1464 ms 56396 KB Output isn't correct
2 Halted 0 ms 0 KB -