oj.uz

Submission #378398

# Submission time Handle Problem Language Result Execution time Memory
378398 2021-03-16T17:04:54 Z qwerty234 Power Plant (JOI20_power) C++14
0 / 100
 4 ms 5228 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back

using namespace std;

const int MAXN = 2e5 + 10, inf = 2e9;

int n, m, d[MAXN], dp[MAXN], a[MAXN];
vector <int> g[MAXN];

void dfs(int u, int p) {
  int smd = 0, mxdp = 0, mxd = 0;
  for (int to : g[u]) {
    if (to == p)
      continue;
    dfs(to, u);
    smd += d[to];
    mxdp = max(mxdp, dp[to]);
    mxd = max(mxd, d[to]);
  }
  d[u] = dp[u] = 0;
  d[u] = max(d[u], max(0, -a[u] + smd));
  dp[u] = max(dp[u], max(mxdp, smd));
  if (a[u] == 1) {
    d[u] = max(d[u], 1);
    dp[u] = max(dp[u], 1 + mxd);
  }
}

main() {
//  freopen("input.txt", "r", stdin);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    g[u].pb(v);
    g[v].pb(u);
  }
  for (int i = 1; i <= n; i++) {
    char ch;
    cin >> ch;
    a[i] = ch - '0';
  }
  dfs(1, -1);
  cout << dp[1];
}

Compilation message

power.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      |      ^

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Incorrect 4 ms 4972 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Incorrect 4 ms 4972 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 4972 KB Output is correct
3 Correct 4 ms 4972 KB Output is correct
4 Correct 4 ms 4972 KB Output is correct
5 Correct 4 ms 4972 KB Output is correct
6 Correct 4 ms 4972 KB Output is correct
7 Correct 4 ms 4972 KB Output is correct
8 Correct 4 ms 4972 KB Output is correct
9 Correct 4 ms 4972 KB Output is correct
10 Correct 4 ms 4972 KB Output is correct
11 Correct 4 ms 4972 KB Output is correct
12 Incorrect 4 ms 4972 KB Output isn't correct
13 Halted 0 ms 0 KB -