Submission #763090

#	Time	Username	Problem	Language	Result	Execution time	Memory
763090		trucmai	Power Plant (JOI20_power)	C++17	100 / 100	128 ms	45540 KiB

power

//#i_love_aisukiuwu#9998

#include <bits/stdc++.h>
using namespace std;

void open(){
  if(fopen("i.inp","r")){
    freopen("i.inp","r",stdin);
    freopen("o.out","w",stdout);
  }
}

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 27;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,dp[MN1],res = -INF;
bool power[MN1]; 
vector<ll>adj[MN1];
//dp[u] la max profit tai subtree u
//dp[u] = max(power[u],sum_{v = G[u]} dp[v] - power[u]) 

void dfs(ll u,ll pre){
	ll sum = 0,mx = 0;
	dp[u] = 1;
	for(ll v : adj[u]){
		if(v == pre) continue;
		dfs(v,u);
		sum += dp[v];
		mx = max(mx,dp[v]);
	}
	dp[u] = max((ll)power[u],sum - power[u]);
	res = max({res,sum - power[u],mx + power[u]});
}

void solve(){
	cin>>n;
	for(ll i = 1;i < n;++i){
		ll u,v;cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(ll i = 1;i <= n;++i){
		char c; cin>>c; 
		power[i] = (c == '1');
	}
	dfs(1,1);
	cout<<res;
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  open();
  ll t = 1; //cin>>t;
  while(t--) solve(); 
  cerr << "\n" << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message (stderr)

power.cpp: In function 'void open()':
power.cpp:8:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |     freopen("i.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
power.cpp:9:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     freopen("o.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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