Submission #528247

#	Time	Username	Problem	Language	Result	Execution time	Memory
528247		ajpiano	Power Plant (JOI20_power)	C++17	100 / 100	156 ms	31308 KiB

power

#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

const int large = 2e5+5;

int n, ans = 0;
vector<bool> power;
vector<int> edges[large];

vector<int> dp;

void dfs(int node, int par){
    int cans = 0;
    if(power[node]) cans = 1;
    int best = 0;
    int csum = 0;
    for(auto &a: edges[node]){
        if(a == par) continue;
        dfs(a,node);
        csum += dp[a];
        best = max(best,dp[a]);
    }
    if(power[node]){
        ans = max(ans,best+1);
        csum--;
    }
    cans = max(cans,csum);
    ans = max(ans,cans);
    dp[node] = cans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    dp.resize(n+1); power.resize(n+1);
    for(int i = 0; i < n-1; i++){
        int u,v; cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        char a; cin >> a;
        if(a == '1') power[i] = 1;
    }
    dfs(1,0);
    cout << ans << "\n";
    return 0;
}

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