제출 #504044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
504044		tgbegimx	무제 (POI11_dyn)	C++17	100 / 100	750 ms	20620 KiB

Main

  #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;
 }

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10