oj.uz

Submission #1098219

# Submission time Handle Problem Language Result Execution time Memory
1098219 2024-10-09T06:32:32 Z Sputnik123 Power Plant (JOI20_power) C++17
0 / 100
 53 ms 117848 KB 
#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(ans, 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;
    for(ll i = 1; i <= n; ++i)
        dp[i] = (s[i] == '1');
    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
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117844 KB Output is correct
2 Correct 50 ms 117744 KB Output is correct
3 Correct 47 ms 117848 KB Output is correct
4 Correct 51 ms 117792 KB Output is correct
5 Correct 49 ms 117844 KB Output is correct
6 Correct 53 ms 117844 KB Output is correct
7 Incorrect 49 ms 117844 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117844 KB Output is correct
2 Correct 50 ms 117744 KB Output is correct
3 Correct 47 ms 117848 KB Output is correct
4 Correct 51 ms 117792 KB Output is correct
5 Correct 49 ms 117844 KB Output is correct
6 Correct 53 ms 117844 KB Output is correct
7 Incorrect 49 ms 117844 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 117844 KB Output is correct
2 Correct 50 ms 117744 KB Output is correct
3 Correct 47 ms 117848 KB Output is correct
4 Correct 51 ms 117792 KB Output is correct
5 Correct 49 ms 117844 KB Output is correct
6 Correct 53 ms 117844 KB Output is correct
7 Incorrect 49 ms 117844 KB Output isn't correct
8 Halted 0 ms 0 KB -