Submission #522061

#	Time	Username	Problem	Language	Result	Execution time	Memory
522061		ivan24	Power Plant (JOI20_power)	C++14	100 / 100	277 ms	28224 KiB

power

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define F first
#define S second

ll min(ll x, ll y){
    return ((x < y) ? x : y);
}

ll max(ll x, ll y){
    return ((x > y) ? x : y);
}

class Tree {
private:
    ll n;
    vi memo,p,b,sz;
    vvi adjList;
    void DFS (ll v){
        //cout << v << endl;
        sz[v] += b[v];
        for (auto u: adjList[v]){
            if (u == p[v]) continue;
            p[u] = v;
            DFS(u);
            sz[v] += sz[u];
        }
    }
    ll dp(ll v){
        if (memo[v] != -1) return memo[v];
        memo[v] = -b[v];
        for (auto u: adjList[v]){
            //cout << v << " -> " << u << endl;
            if (u == p[v]) continue;
            memo[v] += dp(u);
        }
        memo[v] = max(memo[v],b[v]);
        //cout << v << ": " << memo[v] << endl;
        return memo[v];
    }
public:
    Tree(ll _n){
        n = _n;
        p.assign(n,-1);
        memo.assign(n,-1);
        adjList.resize(n);
        sz.assign(n,0);
    }
    void add_edge(ll u, ll v){
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    void set_b(vi _b){
        b.resize(n);
        b = _b;
    }
    ll solve(){
        DFS(0);
        dp(0);
        ll res = 0;
        /*
        cout << "sz: \n";
        for (auto i: sz) cout << i << " ";
        cout << endl;
        */
        for (ll i = 0; n > i; i++){
            ll cur = memo[i];
            if (sz[0] != sz[i]) cur++;
            //cout << i << ": " << cur << endl;
            res = max(res,cur);
        }
        return res;
    }
};

int main(){
    ll n; cin >> n;
    Tree tree(n);
    for (ll i = 0; n-1 > i; i++){
        ll u,v;
        cin >> u >> v;
        u--; v--;
        tree.add_edge(u,v);
    }
    vi b;
    b.resize(n);
    for (ll i = 0; n > i; i++){
        char c; cin >> c;
        b[i] = (c == '1');
    }
    tree.set_b(b);
    cout << tree.solve() << '\n';
}

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