Submission #1098222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098222		Sputnik123	Power Plant (JOI20_power)	C++17	100 / 100	145 ms	142540 KiB

power

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define in insert
#define pll pair<ll,ll>
#define vpl vector<pll>
#define vll vector <ll>
#define vl vector<ll>
#define F first
#define S second
#define ll long long
#define all(v) v.begin(),v.end()
#define endl "\n"
#define ull unsigned long long
#define ld long double
using namespace std;
using namespace __gnu_pbds;
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
const ll sz = 5e6 + 5;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll eps = 1e-12;
const ll P1 = 31; // for hashing
const ll P2 = 41; // for hashing 
//template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// ll idx = 1;
ll n, ans, dp[sz];
vll g[sz];
string s;
void dfs(ll node, ll par = -1)
{
    ll sum = 0, mx = 0;
    ll is = (s[node] == '1');
    for(ll i : g[node])
    {
        if(i == par)
            continue;
        dfs(i, node);
        sum += dp[i];
        mx = max(mx, dp[i]);
    }
    dp[node] = max(is, sum - is);
    ans = max({ans, sum - is, mx + is});
}
void solve()
{   
    cin >> n;
    for(ll i = 1; i < n; i++){
        ll u,  v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin >> s;
    s = '!' + s;
    dfs(1);
    cout << ans << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    long long t = 1;
    // cin >> t;
    while(t--)
    {	   
        // cout << "Case #" << (int) idx <<": ";
        solve();
        // idx++;
    }
}
/* 
Note : don`t use fast input in interactive questions
Note : Compare long double with eps = 1e-12
Note : Always write 2 hashes
*/

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