Submission #298523

#	Time	Username	Problem	Language	Result	Execution time	Memory
298523		BeanZ	Power Plant (JOI20_power)	C++14	100 / 100	217 ms	29752 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 2e5 + 5;
ll dp[N], cur[N];
vector<ll> node[N];
string s;
ll ans = 0;
void dfs(ll u, ll p){
        vector<ll> val;
        for (auto j : node[u]){
                if (j == p) continue;
                dfs(j, u);
                val.push_back(dp[j]);
        }
        if (val.size()){
                sort(val.begin(), val.end(), greater<ll>());
                ans = max(ans, val[0] + (s[u] == '1'));
                ll sum = 0;
                for (auto j : val) sum += j;
                ans = max(ans, sum - (s[u] == '1'));
                dp[u] = max((ll)(s[u] == '1'), sum - (s[u] == '1'));
        } else {
                dp[u] = (s[u] == '1');
                ans = max(ans, dp[u]);
        }
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("A.INP", "r")){
                freopen("A.INP", "r", stdin);
                freopen("A.OUT", "w", stdout);
        }
        ll n;
        cin >> n;
        for (int i = 1; i < n; i++){
                ll u, v;
                cin >> u >> v;
                node[u].push_back(v);
                node[v].push_back(u);
        }
        cin >> s;
        s = " " + s;
        dfs(1, 1);
        cout << ans;
}
/*
7
1 2
1 3
2 4
3 5
1 6
1 7
1001111
*/

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:35:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 |                 freopen("A.INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
power.cpp:36:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   36 |                 freopen("A.OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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