Submission #546187

#	Time	Username	Problem	Language	Result	Execution time	Memory
546187		Deepesson	Power Plant (JOI20_power)	C++17	47 / 100	1559 ms	43592 KiB

power

#include <bits/stdc++.h>
#define MAX 205000LL
std::vector<int> con[MAX];
std::string valores;
typedef std::pair<int,int> pii;
std::unordered_map<long long,int> mapa;

int explora(long long pos,long long prev){
    long long cod = (MAX* pos) + prev;
    if(mapa.find(cod)!=mapa.end())return mapa[cod];
    int ans=0;
    if(valores[pos]=='1')ans=1;
    int soma=0;
    for(auto&x:con[pos]){
        if(x==prev)continue;
        soma+=explora(x,pos);
    }
    if(valores[pos]=='1')--soma;
    mapa[cod]=std::max(ans,soma);
    return std::max(ans,soma);
}

int N;
int ans=0;
int main()
{
    std::cin>>N;
    for(int i=1;i!=N;++i){
        int a,b;
        std::cin>>a>>b;
        --a;--b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    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,i);
            if(valores[i]=='1')other=std::max(other,b+1);
            tot+=b;
        }
        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