oj.uz

답안 #282006

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
282006 2020-08-23T19:00:54 Z stefanbalaz2 Dynamite (POI11_dyn) C++14
70 / 100
 3000 ms 65540 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;
struct node{
    int val,lazy,pos;
};
pii dp2[maxn];
int d[maxn],n,ind[maxn],m,lazy[maxn],h[maxn],e2;
vector<pii>stek[maxn];
vector<node>dp1[maxn];
vector<int>vect[maxn];
void ins(int x,int val,int id){

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

}
void ers(int x,int id){

    while(stek[x].size() && stek[x].back().ss<=id){
        lazy[x]-=stek[x].back().ff+lazy[x];
        stek[x].pop_back();
    }

    return;
}
int get_dp(int x,int id){

    if(id<dp1[x].back().pos)return 1e9;

    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];

    l=0;
    r=dp1[x].size()-1;
    ret=-1;
    while(l<=r){
        sr=(l+r)/2;
        if(dp1[x][sr].pos<=id){
            ret=sr;
            r=sr-1;
        }
        else l=sr+1;
    }

    return min(dp1[x][ret].val+val,dp2[x].ff);
}
void go(int x,int prv,int val){


    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(e2)return;
        if(dp1[ind[x]].size()==0){
            swap(ind[x],ind[id]);
            continue;
        }
        if(dp1[ind[x]][0].pos<dp1[ind[id]][0].pos)swap(ind[x],ind[id]);

        /// 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]].back().pos+(val-dp2[ind[x]].ss-2)),dp2[ind[x]].ss});
            pom=min(pom,{dp2[ind[id]].ff+get_dp(ind[x],dp1[ind[x]].back().pos+(val-dp2[ind[id]].ss-2)),dp2[ind[id]].ss});


            ///dp1

            vector<node>v1,v2;
            int ind1=dp1[ind[x]].size()-1;
            int ind2=dp1[ind[id]].size()-1;
            while(ind1>=0 && ind2>=0){
                if(dp1[ind[x]][ind1].pos>dp1[ind[id]][ind2].pos){
                    v2.pb(dp1[ind[id]].back());
                    dp1[ind[id]].pop_back();
                    ind2--;
                }
                else if(dp1[ind[x]][ind1].pos<dp1[ind[id]][ind2].pos){
                    v1.pb(dp1[ind[x]].back());
                    dp1[ind[x]].pop_back();
                    ind1--;
                }
                else{
                    v1.pb(dp1[ind[x]].back());
                    dp1[ind[x]].pop_back();
                    ind1--;

                    v2.pb(dp1[ind[id]].back());
                    dp1[ind[id]].pop_back();
                    ind2--;
                }
            }

            ind1=0;
            ind2=0;
            int minn1=dp2[ind[x]].ff;
            int minn2=dp2[ind[id]].ff;
            int cnt1=0;
            int cnt2=0;
            vector<node>fin;

            while(ind1<v1.size() || ind2<v2.size()){


                if(ind1>=v1.size()){

                    cnt2+=v2[ind2].lazy;
                    v2[ind2].lazy=0;
                    v2[ind2].val+=cnt2;

                    minn2=min(minn2,v2[ind2].val);

                    fin.pb({minn1+minn2,0,v2[ind2].pos});

                    ind2++;
                }
                else if(ind2>=v2.size()){

                    cnt1+=v1[ind1].lazy;
                    v1[ind1].lazy=0;
                    v1[ind1].val+=cnt1;

                    minn1=min(minn1,v1[ind1].val);

                    fin.pb({minn1+minn2,0,v1[ind1].pos});

                    ind1++;
                }
                else if(v1[ind1].pos==v2[ind2].pos){

                    cnt1+=v1[ind1].lazy;
                    v1[ind1].lazy=0;
                    v1[ind1].val+=cnt1;

                    cnt2+=v2[ind2].lazy;
                    v2[ind2].lazy=0;
                    v2[ind2].val+=cnt2;

                    minn1=min(minn1,v1[ind1].val);
                    minn2=min(minn2,v2[ind2].val);

                    fin.pb({minn1+minn2,0,v1[ind1].pos});

                    ind2++;
                    ind1++;
                }
                else if(v1[ind1].pos>v2[ind2].pos){/// prvo v2

                    cnt2+=v2[ind2].lazy;
                    v2[ind2].lazy=0;
                    v2[ind2].val+=cnt2;

                    minn2=min(minn2,v2[ind2].val);

                    fin.pb({minn1+minn2,0,v2[ind2].pos});

                    ind2++;
                }
                else{

                    cnt1+=v1[ind1].lazy;
                    v1[ind1].lazy=0;
                    v1[ind1].val+=cnt1;

                    minn1=min(minn1,v1[ind1].val);

                    fin.pb({minn1+minn2,0,v1[ind1].pos});

                    ind1++;
                }
            }


            ers(x,fin.back().pos);
            ins(x,cnt1+minn2,fin.back().pos);
            fin[fin.size()-1].val-=cnt1+minn2;
            fin[fin.size()-1].lazy+=cnt1+minn2;

            while(fin.size()){
                dp1[ind[x]].pb(fin.back());
                fin.pop_back();
            }


            dp2[ind[x]]=pom;
    }


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

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

        return;
    }


    dp2[ind[x]].ss++;
    pii pom;
    pom={min(dp2[ind[x]].ff,get_dp(ind[x],dp1[ind[x]].back().pos+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;


    int cnt1=0;
    int last=-2;
    while(dp1[ind[x]].size()){
        if(cnt1+dp1[ind[x]].back().lazy+dp1[ind[x]].back().val<dp2[ind[x]].ff)break;

        cnt1+=dp1[ind[x]].back().lazy;
        last=dp1[ind[x]].back().pos;
        dp1[ind[x]].pop_back();
    }
    ers(ind[x],last);
    if(dp1[ind[x]].size()>0){
        dp1[ind[x]][dp1[ind[x]].size()-1].lazy+=cnt1;
        ins(ind[x],cnt1,dp1[ind[x]].back().pos);
    }
    dp1[ind[x]].pb({dp2[ind[x]].ff,0,h[x]});

    dp2[ind[x]]=pom;


    if(dp2[ind[x]].ff>m)e2=1;

}
bool check(int x){

    e2=0;
    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(e2)return false;

    int ret=dp2[ind[1]].ff;

    if(ret<=m)return true;
    else return false;
}
void hp(int x,int prv,int hh){

    h[x]=hh;
    for(int i=0;i<vect[x].size();i++){
        int id=vect[x][i];
        if(id==prv)continue;
        hp(id,x,hh+1);
    }
}
int main(){

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

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


    hp(1,0,1);

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


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

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

    }

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

    return 0;
}

Compilation message

dyn.cpp: In function 'void go(int, int, int)':
dyn.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int j=0;j<vect[x].size();j++){
      |                 ~^~~~~~~~~~~~~~~
dyn.cpp:141:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             while(ind1<v1.size() || ind2<v2.size()){
      |                   ~~~~^~~~~~~~~~
dyn.cpp:141:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |             while(ind1<v1.size() || ind2<v2.size()){
      |                                     ~~~~^~~~~~~~~~
dyn.cpp:144:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |                 if(ind1>=v1.size()){
      |                    ~~~~^~~~~~~~~~~
dyn.cpp:156:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |                 else if(ind2>=v2.size()){
      |                         ~~~~^~~~~~~~~~~
dyn.cpp: In function 'void hp(int, int, int)':
dyn.cpp:293:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  293 |     for(int i=0;i<vect[x].size();i++){
      |                 ~^~~~~~~~~~~~~~~
dyn.cpp: In function 'int main()':
dyn.cpp:304:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  304 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dyn.cpp:305:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  305 |     for(int i=1;i<=n;i++)scanf("%d",&d[i]);
      |                          ~~~~~^~~~~~~~~~~~
dyn.cpp:308:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  308 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 16 ms 23800 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 20 ms 23936 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 24704 KB Output is correct
2 Correct 109 ms 25468 KB Output is correct
3 Correct 147 ms 26616 KB Output is correct
4 Correct 140 ms 32248 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 347 ms 28920 KB Output is correct
2 Correct 546 ms 29816 KB Output is correct
3 Correct 652 ms 29324 KB Output is correct
4 Correct 675 ms 41336 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 911 ms 33148 KB Output is correct
2 Correct 930 ms 32376 KB Output is correct
3 Correct 653 ms 30648 KB Output is correct
4 Correct 1135 ms 50424 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2176 ms 41596 KB Output is correct
2 Correct 2391 ms 41464 KB Output is correct
3 Runtime error 395 ms 65540 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3089 ms 53728 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 441 ms 65540 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -