Submission #293672

#	Time	Username	Problem	Language	Result	Execution time	Memory
293672		AlexLuchianov	Power Plant (JOI20_power)	C++14	0 / 100	4 ms	4992 KiB

power

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <algorithm>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
std::vector<int> g[1 + nmax];
char active[1 + nmax];
int dp[1 + nmax];

void dfs(int node, int parent) {
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    if(to == parent)
      g[node].erase(g[node].begin() + h);
  }

  dp[node] = -(active[node] - '0');

  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    dfs(to, node);
    dp[node] += dp[to];
  }
  dp[node] = std::max(dp[node], active[node] - '0');
}

int solve(int node) {
  int result = 0;
  for(int h = 0; h < g[node].size(); h++) {
    int to = g[node][h];
    result = std::max(result, solve(to));
    result = std::max(result, dp[to] + active[node] - '0');
  }
  return result;
}

int main() {
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  for(int i = 1; i < n; i++) {
    int a, b;
    std::cin >> a >> b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  std::cin >> (active + 1);
  dfs(1, 0);
  std::cout << solve(1);

  return 0;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int)':
power.cpp:17:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
power.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~
power.cpp: In function 'int solve(int)':
power.cpp:35:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for(int h = 0; h < g[node].size(); h++) {
      |                  ~~^~~~~~~~~~~~~~~~

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