Submission #293119

#	Time	Username	Problem	Language	Result	Execution time	Memory
293119		Berted	Power Plant (JOI20_power)	C++14	100 / 100	228 ms	32564 KiB

power

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 1e9;

int n, dp[200001][2];
vector<int> adj[200001];
string s;

void DFS(int u, int p)
{
	dp[u][0] = dp[u][1] = -INF;
	int mx1 = -INF, mx2 = -INF;
	vector<int> val;
	for (auto v : adj[u])
	{
		if (v != p)
		{
			DFS(v, u);
			mx1 = max(mx1, dp[v][0]);
			mx2 = max(mx2, dp[v][1]);
			val.push_back(dp[v][1]);
		}
	}
	sort(val.begin(), val.end(), greater<int>());
	int S = 0, i;
	for (i = 0; i < val.size() && val[i] > 0; i++) {S += val[i];}
	if (s[u] == '1') {dp[u][0] = dp[u][1] = 1;}
	dp[u][0] = max(dp[u][0], mx1);
	dp[u][0] = max(dp[u][0], mx2 + (s[u] == '1'));
	if (i > 1) dp[u][0] = max(dp[u][0], S - (s[u] == '1'));
	dp[u][1] = max(dp[u][1], mx2 - (s[u] == '1'));
	if (i > 1) dp[u][1] = max(dp[u][1], S - (s[u] == '1'));
	//cout << u << " " << dp[u][0] << " " << dp[u][1] << "\n";
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		adj[u - 1].push_back(v - 1);
		adj[v - 1].push_back(u - 1);
	}
	cin >> s;

	DFS(0, -1);
	cout << dp[0][0] << "\n";

	return 0;
}

Compilation message (stderr)

power.cpp: In function 'void DFS(int, int)':
power.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (i = 0; i < val.size() && val[i] > 0; i++) {S += val[i];}
      |              ~~^~~~~~~~~~~~

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