Submission #298889

#	Time	Username	Problem	Language	Result	Execution time	Memory
298889		toloraia	Power Plant (JOI20_power)	C++14	100 / 100	264 ms	28280 KiB

power

#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
#define int long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
/*
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")

#pragma GCC target("avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")

#pragma comment(linker, "/STACK: 20000000005")
*/

using namespace std;

const int N = 200005;

int n, ans;
int c[N];
int dp[N], DP[N];
vector < int > g[N];

void dfs (int k, int p){
    for (int to : g[k]){
        if (to == p)
            continue;
        dfs (to, k);
        dp[k] += dp[to];
    }
    dp[k] = max (dp[k] - c[k], c[k]);
}

void go (int k, int p, int X){
    int sum = 0;
    ans = max (ans, c[k] + X);
    for (int to : g[k]){
        if (to == p)
            continue;
        sum += dp[to];
        ans = max (ans, c[k] + dp[to]);
    }
    sum += X;
    ans = max (ans, sum - c[k]);
    for (int to : g[k]){
        if (to == p)
            continue;
        sum -= dp[to];
        int mx = max (c[k], sum - c[k]);
        go (to, k, mx);
        sum += dp[to];
    }
}

main()
{
    //freopen ("in.in", "r", stdin);freopen ("out.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin >> n;
    for (int u, v, i = 1; i < n; i++){
        cin >> u >> v;
        g[u].pb (v);
        g[v].pb (u);
    }
    char ch;
    for (int i = 1; i <= n; i++){
        cin >> ch;
        c[i] = ch - '0';
        c[0] += c[i];
    }
    if (c[0] >= 2)
        ans = 2;
    else
        ans = c[0];
    dfs (1, 0);
    go (1, 0, 0);
    cout << ans << endl;
}

Compilation message (stderr)

power.cpp:19:1: warning: "/*" within comment [-Wcomment]
   19 | /*
      |  
power.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main()
      |      ^

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