Submission #546192

#	Time	Username	Problem	Language	Result	Execution time	Memory
546192		Deepesson	Power Plant (JOI20_power)	C++17	47 / 100	1581 ms	35928 KiB

power

#include <bits/stdc++.h>
#define MAX 505000LL
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
std::string valores;
bool existe[MAX*2];
int tab[MAX*2];
int count=0;
int explora(long long pos,long long prev,int ind){
    if(existe[ind])return tab[ind];
    existe[ind]=true;
    count++;
    int ans=0;
    if(valores[pos]=='1')ans=1;
    int soma=0;
    for(auto&x:con[pos]){
        if(x.first==prev)continue;
        soma+=explora(x.first,pos,x.second);
    }
    if(valores[pos]=='1')--soma;
    return tab[ind]=std::max(ans,soma);
}

int N;
int ans=0;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int cur=0;
    std::cin>>N;
    for(int i=1;i!=N;++i){
        int a,b;
        std::cin>>a>>b;
        --a;--b;
        con[a].push_back({b,cur++});
        con[b].push_back({a,cur++});
    }
    std::cin>>valores;
    for(int i=0;i!=N;++i){
        int tot=0;
        int other=0;
        for(auto&x:con[i]){
            int b = explora(x.first,i,x.second);
            if(valores[i]=='1')other=std::max(other,b+1);
            tot+=b;
        }
        assert(count<MAX*2);
        if(valores[i]=='1'){
            --tot;
            tot=std::max(tot,1);
        }
        ans=std::max(ans,tot);
        ans=std::max(ans,other);
    }
    assert(ans);
    std::cout<<ans<<"\n";
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 0 / 53