Submission #1087221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087221		peacebringer1667	Power Plant (JOI20_power)	C++17	100 / 100	99 ms	29860 KiB

power

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e5 + 5;
const int inf = 1e8;

bool a[maxn];
int dp[maxn],f[maxn];
vector <vector<int>> vec(maxn);

void input(int n){
	for (int i = 1 ; i < n ; i++){
		int u,v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	
	string s;
	cin >> s;
	for (int i = 0 ; i < s.size() ; i++)
	  a[i + 1] = s[i] - 48;
}


void dfs(int u,int par){
	int t = -a[u];
	dp[u] = a[u];
	f[u] = a[u];
	
	for (int v : vec[u])
	  if (v != par){
	  	dfs(v,u);
	  	t += dp[v];
	  	
	  	f[u] = max(f[u],a[u] + dp[v]);
	  }
	
	dp[u] = max(dp[u],t);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	freopen("power.inp","r",stdin);
//	freopen("power.out","w",stdout);
	int n;
	cin >> n;
	input(n);
	
	dfs(1,0);
	int res = 0;
	for (int i = 1 ; i <= n ; i++) res = max(res,max(dp[i],f[i]));
	
	cout << res;

	return 0;
}

Compilation message (stderr)

power.cpp: In function 'void input(int)':
power.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0 ; i < s.size() ; i++)
      |                   ~~^~~~~~~~~~

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