Submission #762982

#	Time	Username	Problem	Language	Result	Execution time	Memory
762982		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	149 ms	27032 KiB

power

#include<bits/stdc++.h>
using namespace std;
vector<int> ad[200001];
int dp[200001][2];
bool visited[200001], light[200001];
void dfs(int u)
{
    visited[u] = 1;
    for(int v : ad[u]) if(visited[v] == 0) dfs(v);
    int sum = 0;
    for(int v : ad[u]) if(visited[v] == 0) sum += dp[v][1];
    dp[u][1] = max((int)light[u], sum - light[u]);
    //calculate dp[u][0]
    //Not activated case
    int maxdif = 0, case1 = 0;
    for(int v : ad[u]) if(visited[v] == 0){
        maxdif = max(maxdif, max(dp[v][0], dp[v][1]));
        case1 += dp[v][1];
    }
    if(ad[u].size()+(u==1) > 2) case1 -= light[u];
    case1 = max(case1, maxdif);
    //Activated case
    int case2 = 0, sumcase = 0;
    for(int v : ad[u]) if(visited[v] == 0){
        case2 = max(case2, dp[v][1]);
        sumcase += dp[v][1];
    }
    if(ad[u].size()+(u==1) > 2) sumcase -= light[u];
    case2 += light[u];
    case2 = max(case2, sumcase);
    dp[u][0] = max(case1, case2);
    visited[u] = 0;
    //cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i = 0; i < n-1; i++){
        int u, v;
        cin>>u>>v;
        ad[u].push_back(v);
        ad[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        char x;
        cin>>x;
        light[i] = (x == '1');
    }
    dfs(1);
    cout<<max(dp[1][0], dp[1][1]);
}

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