Submission #1095377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095377		ro9669	Power Plant (JOI20_power)	C++17	100 / 100	79 ms	28876 KiB

power

#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) int(v.size())
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(2e5)+7;
const int inf = int(1e9)+7;

int n;
vector<int> g[maxN];
string s;
int dp[maxN] , ans = -inf;

void dfs(int u , int par){
    dp[u] = (s[u] - '0');
    int preSum = 0;
    for (int v : g[u]){
        if (v != par){
            dfs(v , u);
            preSum += max(dp[v] , 0);
            ans = max(ans , dp[v] + (s[u] - '0'));
        }
    }
    ans = max(ans , preSum - (s[u] - '0'));
    ans = max(ans , s[u] - '0');
    for (int v : g[u]){
        if (v != par){
            dp[u] = max(dp[u], preSum - max(dp[v] , 0) + dp[v] - (s[u] - '0'));
        }
    }
}

void solve(){
    cin >> n;
    //assert(n <= 2000);
    for (int i = 1 ; i < n ; i++){
        int u , v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    cin >> s; s = '#' + s;
    for (int i = 1 ; i <= n ; i++){
        dfs(i , 0);
        break;
    }
    cout << ans << "\n";
}

#define name "A"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(name".INP" , "r")){
        freopen(name".INP" , "r" , stdin);
        freopen(name".OUT" , "w" , stdout);
    }
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(name".INP" , "r" , stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(name".OUT" , "w" , stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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