oj.uz

Submission #394373

# Submission time Handle Problem Language Result Execution time Memory
394373 2021-04-26T12:55:22 Z parsabahrami Power Plant (JOI20_power) C++17
0 / 100
 4 ms 4960 KB 
/* There's someone in my head but it's not me */ 
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 2e5 + 10, MOD = 1e9 + 7;
int dp[N], pd[N], M[N], n, rt; vector<int> adj[N];
int ret = 0;

void DFS(int v, int p = -1) {
    for (int u : adj[v]) 
        if (u != p) DFS(u, v);
    int sum = 0;
    for (int u : adj[v]) 
        if (u != p) sum += dp[u];
    for (int u : adj[v])
        if (u != p) 
            dp[v] = max(dp[v], dp[u] - M[v]);
    dp[v] = max(dp[v], sum - M[v]);
    dp[v] = max(dp[v], M[v]); 
    ret = max(ret, sum + M[v]);
  	if (~p) ret = max(ret, dp[v] + M[p]);
    //printf("%d %d\n", v, dp[v]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    scanf("\n");
    for (int i = 1; i <= n; i++) {
        char c; scanf("%c", &c);
        if (c - '0') M[i] = 1, rt = i;
    }
    DFS(rt);
    printf("%d\n", max(dp[rt], ret));
    return 0;
}

Compilation message

power.cpp: In function 'int main()':
power.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
power.cpp:36:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |         int u, v; scanf("%d%d", &u, &v);
      |                   ~~~~~^~~~~~~~~~~~~~~~
power.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |     scanf("\n");
      |     ~~~~~^~~~~~
power.cpp:42:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |         char c; scanf("%c", &c);
      |                 ~~~~~^~~~~~~~~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4960 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Incorrect 3 ms 4940 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4960 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Incorrect 3 ms 4940 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 4960 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Incorrect 3 ms 4940 KB Output isn't correct
7 Halted 0 ms 0 KB -