Submission #394363

#	Time	Username	Problem	Language	Result	Execution time	Memory
394363		parsabahrami	Power Plant (JOI20_power)	C++17	0 / 100	3 ms	4940 KiB

power

/* 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]); 
    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", ret);
    return 0;
}

Compilation message (stderr)

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

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