oj.uz

Submission #293672

# Submission time Handle Problem Language Result Execution time Memory
293672 2020-09-08T09:34:55 Z AlexLuchianov Power Plant (JOI20_power) C++14
0 / 100
 4 ms 4992 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -