Submission #763352

#	Time	Username	Problem	Language	Result	Execution time	Memory
763352		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	131 ms	27272 KiB

power

#include<bits/stdc++.h>
using namespace std;

#define taskname "template"
#define ll long long
#define ld double
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int> 
#define vii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MN=2e5+5;

int n;
int a,b;
string s;
vi son[MN];
pii dp[MN];
int ans;

void dfs(int u,int par){
    int cnt=0,max1=0;
    for(int v:son[u]){
        if(v==par) continue;
        dfs(v,u);
        dp[u].fi+=dp[v].fi;
        max1=max(max1,dp[v].fi);
    }
    ans=max({ans,max1+(s[u]=='1'),dp[u].fi-(s[u]=='1')});
    dp[u].fi = max(dp[u].fi - (s[u] == '1'), (s[u] - '0'));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    /*
    freopen(taskname".inp","r",stdin);
    freopen(taskname".out","w",stdout);
    */
    cin>>n;
    for(int i=1;i<n;++i){
        cin>>a>>b;
        son[a].eb(b); son[b].eb(a);
    }
    
    cin>>s;
    s='#'+s;
    dfs(1,0);
    
    // for(int i=1;i<=n;++i){
    //     cout<<"Case "<<i<<": "<<dp[i].fi<<'\n';
    // }
    cout<<ans<<'\n';
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int)':
power.cpp:28:9: warning: unused variable 'cnt' [-Wunused-variable]
   28 |     int cnt=0,max1=0;
      |         ^~~

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