Submission #292590

#	Time	Username	Problem	Language	Result	Execution time	Memory
292590		Pajaraja	Power Plant (JOI20_power)	C++17	100 / 100	412 ms	21484 KiB

power

#include <bits/stdc++.h>
#define MAXN 200007
using namespace std;
int dp[MAXN],sol=0,pg[MAXN];
vector<int> g[MAXN];
void dfs(int s,int f)
{
	for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
	dp[s]=pg[s];
	int sum=0;
	for(int i=0;i<g[s].size();i++) sol=max(sol,dp[g[s][i]]+pg[s]);
	for(int i=0;i<g[s].size();i++) sum+=dp[g[s][i]];
	dp[s]=max(dp[s],sum-pg[s]);
	sol=max(sol,dp[s]);
}
int main()
{
	int n;
	cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int t1,t2;
		cin>>t1>>t2;
		g[t1].push_back(t2);
		g[t2].push_back(t1);
	}
	string s;
	cin>>s;
	for(int i=0;i<n;i++) pg[i+1]=s[i]-'0';
	dfs(1,1);
	cout<<sol;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(int, int)':
power.cpp:8:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
      |              ~^~~~~~~~~~~~
power.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int i=0;i<g[s].size();i++) sol=max(sol,dp[g[s][i]]+pg[s]);
      |              ~^~~~~~~~~~~~
power.cpp:12:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i=0;i<g[s].size();i++) sum+=dp[g[s][i]];
      |              ~^~~~~~~~~~~~

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