oj.uz

Submission #279756

# Submission time Handle Problem Language Result Execution time Memory
279756 2020-08-22T10:49:47 Z stefanbalaz2 Dynamite (POI11_dyn) C++14
40 / 100
 3000 ms 45432 KB 
/*



*/
#include<bits/stdc++.h>
#include<set>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define ll long long
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
const int maxn=3e5+10;
pii dp2[maxn];
int d[maxn],n,ind[maxn],m,lazy[maxn];
vector<pii>stek[maxn],dp1[maxn];
vector<int>vect[maxn];
void ins(int x,int val,int id){

    ///printf("%d  ALZY\n",lazy);

    if(stek[x].size()==0){
        stek[x].pb({-lazy[x],id});
        lazy[x]+=val;
        return;
    }

    if(stek[x].back().ss==id)lazy[x]+=val;
    else{
        stek[x].pb({-lazy[x],id});
        lazy[x]+=val;
    }

   /// printf("%d  ALZY\n",lazy);
}
void ers(int x,int id){
    ///printf("%d  ALZY22\n",lazy);
    while(stek[x].size() && stek[x].back().ss>=id){
        lazy[x]-=stek[x].back().ff+lazy[x];
        stek[x].pop_back();
    }
    ///printf("%d  ALZY22\n",lazy);
    return;
}
/*int get_dp(int x,int id){

    if(id>=(int)dp1[x].size())return 1e9;
    id=max(id,0);

    int l=0;
    int r=stek[x].size()-1;
    int ret=-1,sr;

    while(l<=r){
        sr=(l+r)/2;
        if(stek[x][sr].ss>=id){
            ret=sr;
            r=sr-1;
        }
        else l=sr+1;
    }
    int val=0;
    if(ret!=-1)val=stek[x][ret].ff+lazy[x];

    ///printf("%d %d %d JOOOJ\n",dp1[x][id].ff,val,lazy[x]);
    return dp1[x][id].ff+val;
}*/
int get_dp(int x,int id){

    if(id>=(int)dp1[x].size())return 1e9;
    id=max(id,0);

    int ret=1e9;
    for(int i=dp1[x].size()-1;i>=id;i--){
        dp1[x][i].ff+=dp1[x][i].ss;
        if(i-1>=0)dp1[x][i-1].ss+=dp1[x][i].ss;
        dp1[x][i].ss=0;
        ret=min(ret,dp1[x][i].ff);
    }

    return ret;
}
void ispis(int x){

    for(int i=dp1[x].size()-1;i>=0;i--)printf("%d %d | ",dp1[x][i].ff,dp1[x][i].ss);
    printf("\n");
}
void go(int x,int prv,int val){

    ///printf("%d %d AAAA\n",x,prv);

    ind[x]=x;
    for(int j=0;j<vect[x].size();j++){
        int id=vect[x][j];
        if(id==prv)continue;

        go(id,x,val);
        if(dp1[ind[x]].size()<dp1[ind[id]].size())swap(ind[x],ind[id]);

        ///printf("%d IDIDIDID\n",id);
        ///if(dp1[ind[x]].size()>0)printf("%d %d | %d %d !!! %d %d \n",dp2[ind[x]].ff,dp2[ind[x]].ss,dp1[ind[x]][0].ff,dp1[ind[x]][0].ss,dp1[ind[x]][1].ff,dp1[ind[x]][1].ss);
        ///if(dp1[ind[id]].size()>0)printf("%d %d | %d %d !!! %d %d \n",dp2[ind[id]].ff,dp2[ind[id]].ss,dp1[ind[id]][0].ff,dp1[ind[id]][0].ss,dp1[ind[id]][1].ff,dp1[ind[id]][1].ss);

        if(dp1[ind[id]].size()==0)continue;

        /// merge trees

            /// dp2
            pii pom;
            pom={dp2[ind[x]].ff+dp2[ind[id]].ff,min(dp2[ind[x]].ss,dp2[ind[id]].ss)};
            pom=min(pom,{dp2[ind[x]].ff+get_dp(ind[id],dp1[ind[id]].size()-(val-dp2[ind[x]].ss-2)-2),dp2[ind[x]].ss});
            pom=min(pom,{dp2[ind[id]].ff+get_dp(ind[x],dp1[ind[x]].size()-(val-dp2[ind[id]].ss-2)-2),dp2[ind[id]].ss});


            ///dp1
            int cnt1=0,cnt2=0;
            int ind1=dp1[ind[x]].size()-1;
            int ind2=dp1[ind[id]].size()-1;

            for(int i=dp1[ind[x]].size()-1;i>=max(0,/*(int)dp1[ind[id]].size()-val-2*/0);i--){

                if(ind2<0)ind2=0;

                cnt1=dp1[ind[x]][ind1].ss;
                cnt2=dp1[ind[id]][ind2].ss;
                ers(ind[x],ind1);
                ers(ind[id],ind2);
                dp1[ind[x]][ind1].ss=0;
                dp1[ind[id]][ind2].ss=0;

                dp1[ind[x]][ind1].ff+=cnt1;
                dp1[ind[id]][ind2].ff+=cnt2;


                ///dp1[ind[x]][ind1].ff+=min(dp1[ind[id]][ind2].ff,dp2[ind[id]].ff);
                dp1[ind[x]][ind1].ff=get_dp(ind[id],ind2)+get_dp(ind[x],ind1);

                ///printf("%d %d | %d %d || %d\n",dp1[ind[x]][ind1].ff,dp1[ind[id]][ind2].ff,ind1,ind2,x);

                ind1--;
                ind2--;

                ins(ind[x],cnt1,ind1);
                if(ind1>0)dp1[ind[x]][ind1].ss+=cnt1;
                ins(ind[id],cnt2,ind2);
                if(ind2>0)dp1[ind[id]][ind2].ss+=cnt2;
            }

            /*ind2++;
            if(ind1>0)dp1[ind[x]][ind1].ss+=min(dp1[ind[id]][ind2].ff,dp2[ind[id]].ff);
            ins(ind[x],min(dp1[ind[id]][ind2].ff,dp2[ind[id]].ff),ind1);*/


            /// mozda ovaj na 0tom mestu mora posebno da se racuna, da li je on manji od ostalog?
            dp1[ind[x]][dp1[ind[x]].size()-1].ff=pom.ff;
            dp2[ind[x]]=pom;
    }

    ///printf("%d  %d  XXXXLAZYYYYY\n",lazy,x);

    if(dp1[ind[x]].size()==0){

        if(d[x]){
            dp1[ind[x]].pb({0,0});
            dp1[ind[x]].pb({1,0});
            dp2[ind[x]]={1,0};
        }
        else{
            dp1[ind[x]].pb({0,0});
            dp1[ind[x]].pb({0,0});
            dp2[ind[x]]={0,1e8};
        }

         /*printf("%d XX\n",x);
        printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss);
        ispis(ind[x]);*/

        return;
    }

    /*printf("%d XX\n",x);
    printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss);
    ispis(ind[x]);*/

    dp2[ind[x]].ss++;
    pii pom;
    ///printf("%d LAZYYYYY\n",lazy);
    ///printf("%d %d AAAAA\n",get_dp(ind[x],dp1[ind[x]].size()-val-1),dp1[ind[x]].size()-val-1);
    pom={min(dp2[ind[x]].ff,get_dp(ind[x],dp1[ind[x]].size()-val-1))+1,0};
    if(d[x]==0 || dp2[ind[x]].ss<=val)pom=min(pom,dp2[ind[x]]);
    ///if(pom.ff==0)pom.ss=1e8;

    ers(ind[x],dp1[ind[x]].size()-1);
    ins(ind[x],dp1[ind[x]][dp1[ind[x]].size()-1].ss,dp1[ind[x]].size()-2);
    if(dp1[ind[x]].size()>1)dp1[ind[x]][dp1[ind[x]].size()-2].ss=dp1[ind[x]][dp1[ind[x]].size()-1].ss;
    dp1[ind[x]][dp1[ind[x]].size()-1].ss=0;
    dp1[ind[x]][dp1[ind[x]].size()-1]={min(dp2[ind[x]].ff,pom.ff),0};


    dp1[ind[x]].pb({pom.ff,0});
    dp2[ind[x]]=pom;

    /*printf("%d XX\n",x);
    printf("%d %d | \n",dp2[ind[x]].ff,dp2[ind[x]].ss);
    ispis(ind[x]);*/

}
bool check(int x){

    memset(dp2,0,sizeof(dp2));
    for(int i=1;i<=n;i++){
        dp1[i].clear();
        stek[i].clear();
        lazy[i]=0;
    }

    go(1,0,x);
    if(dp2[ind[1]].ff<=m)return true;
    else return false;
}
int main(){

    ///freopen("test2.txt","r",stdin);
    ///freopen("out.txt","w",stdout);

    /// OPTIMISATION WHEN IT CANT SOLVE A SUBTREE THEN BREAK ALL
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&d[i]);
    ///if(n>10000)return 123;

    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d %d",&u,&v);
        vect[u].pb(v);
        vect[v].pb(u);
    }

    int l=0;
    int r=n;
    int sr,ret=-1;

    while(l<=r){
        sr=(l+r)/2;

        ///printf("%d %d %d AAA\n",l,sr,r);

        if(check(sr)){
            ret=sr;
            r=sr-1;
        }
        else l=sr+1;

    }
    ///printf("%d CEHCK\n",check(5));
    ///printf("%d CEHCK\n",check(1));

    printf("%d\n",ret);

    return 0;
}

Compilation message

dyn.cpp: In function 'void go(int, int, int)':
dyn.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int j=0;j<vect[x].size();j++){
      |                 ~^~~~~~~~~~~~~~~
dyn.cpp: In function 'int main()':
dyn.cpp:229:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  229 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dyn.cpp:230:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  230 |     for(int i=1;i<=n;i++)scanf("%d",&d[i]);
      |                          ~~~~~^~~~~~~~~~~~
dyn.cpp:235:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  235 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 16 ms 23912 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 26 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 23928 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 23972 KB Output is correct
2 Correct 19 ms 23928 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 25012 KB Output is correct
2 Correct 136 ms 25720 KB Output is correct
3 Incorrect 164 ms 26576 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 29432 KB Output is correct
2 Correct 612 ms 30876 KB Output is correct
3 Correct 732 ms 30456 KB Output is correct
4 Execution timed out 3085 ms 34936 KB Time limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 33592 KB Output is correct
2 Correct 872 ms 32760 KB Output is correct
3 Correct 958 ms 30756 KB Output is correct
4 Execution timed out 3050 ms 39208 KB Time limit exceeded

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 41464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 45176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 45432 KB Time limit exceeded
2 Halted 0 ms 0 KB -