Submission #1163228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163228		hainam2k9	Power Plant (JOI20_power)	C++20	100 / 100	89 ms	33608 KiB

power

#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
struct Data{
    int val,state,cnt;
}dp[MAXN];
int n,x,y,gen[MAXN],rs=0;
vector<int> adj[MAXN];
void dfs(int u, int par){
    dp[u].val=dp[u].state=dp[u].cnt=0;
    for(int v : adj[u]){
        if(v==par) continue;
        dfs(v,u);
        int val=max(dp[v].val-(dp[v].state==0 ? gen[v] : 0), gen[v]);
        if(val>0) ++dp[u].cnt, dp[u].state+=dp[v].state, dp[u].val+=val;
    }
    dp[u].state+=dp[u].cnt>1;
    if(dp[u].state) dp[u].val-=gen[u];
    else dp[u].val+=gen[u];
}
void reroot(int u, int par){
    rs=max(rs,dp[u].val);
    for(int v : adj[u]){
        if(v==par) continue;
        Data preU=dp[u], preV=dp[v];
        int val=max(dp[v].val-(dp[v].state==0 ? gen[v] : 0), gen[v]);
        if(val>0){
            if(dp[u].state&&dp[u].state-dp[v].state-(dp[u].cnt-1<=1)<=0) dp[u].val+=2*gen[u];
            if(dp[u].cnt==2) --dp[u].state;
            --dp[u].cnt, dp[u].state-=dp[v].state, dp[u].val-=val;
        }
        val=max(dp[u].val-(dp[u].state==0 ? gen[u] : 0), gen[u]);
        if(val>0){
            if(!dp[v].state&&dp[u].state+dp[v].cnt>0) dp[v].val-=2*gen[v];
            if(dp[v].cnt==1) ++dp[v].state;
            ++dp[v].cnt, dp[v].state+=dp[u].state, dp[v].val+=val;
        }
        reroot(v,u);
        dp[u]=preU, dp[v]=preV;
    }
}
int main()
{
    tt;
    if(fopen((NAME + ".INP").c_str(), "r")) fo;
    cin >> n;
    for(int i = 1; i<n; ++i)
        cin >> x >> y, adj[x].pb(y), adj[y].pb(x);
    for(int i = 1; i<=n; ++i){
        char c;
        cin >> c;
        gen[i]=c-'0';
    }
    dfs(1,0);
    reroot(1,0);
    cout << rs;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:3:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:63:45: note: in expansion of macro 'fo'
   63 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~
power.cpp:3:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    3 | #define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
      |                                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:63:45: note: in expansion of macro 'fo'
   63 |     if(fopen((NAME + ".INP").c_str(), "r")) fo;
      |                                             ^~

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