Submission #516322

#	Time	Username	Problem	Language	Result	Execution time	Memory
516322		qwerasdfzxcl	Power Plant (JOI20_power)	C++14	100 / 100	182 ms	27544 KiB

power

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int INF = 1e9;
vector<int> adj[200200];
int dp[200200][3];
char on[200200];

void dfs(int s, int pa = -1){
    //printf("IN: %d\n", s);
    dp[s][1] = 0, dp[s][2] = -INF;
    for (auto &v:adj[s]) if (v!=pa){
        dfs(v, s);
    }

    ///Case 1-1. 루트가 꺼져있고, 2개이상 서브트리에서 선택
    int tmp = 0, val = 0;
    if (on[s]=='1') tmp = -1;
    for (auto &v:adj[s]) if (v!=pa){
        val += max(dp[v][1], dp[v][2] - 2);
    }
    dp[s][1] = max(dp[s][1], val + tmp);

    ///Case 1-2. 루트가 꺼져있고, 서브트리 1개에서 선택
    for (auto &v:adj[s]) if (v!=pa){
        dp[s][1] = max(dp[s][1], dp[v][1]+tmp);
        dp[s][2] = max(dp[s][2], dp[v][2]+tmp);
    }

    ///Case 2. 루트가 켜져있을 때 (강제로 서브트리 1개에서만 선택)
    if (on[s]=='1'){
        dp[s][1] = max(dp[s][1], 1); ///루트만 선택
        for (auto &v:adj[s]) if (v!=pa){
            dp[s][2] = max(dp[s][2], max(dp[v][1]+1, dp[v][2]+1-2));
        }
    }

    dp[s][0] = max(dp[s][1], dp[s][2]);

    //printf("%d: %d %d\n", s, dp[s][1], dp[s][2]);
    //printf("OUT: %d\n", s);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i=0;i<n-1;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    scanf("%s", on+1);

    dfs(1);
    int ans = 0;
    for (int i=1;i<=n;i++) ans = max(ans, dp[i][0]);
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
power.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%s", on+1);
      |     ~~~~~^~~~~~~~~~~~

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