Submission #296140

#	Time	Username	Problem	Language	Result	Execution time	Memory
296140		Pyqe	Power Plant (JOI20_power)	C++14	100 / 100	426 ms	38152 KiB

power

#include <bits/stdc++.h>

using namespace std;

long long n,dp[200069];
bitset<200069> a,vtd;
vector<long long> al[200069],dpl[200069];

void bd(long long x)
{
	long long i,sz=al[x].size(),l;
	
	vtd[x]=1;
	dp[x]=-a[x];
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(!vtd[l])
		{
			bd(l);
			dp[x]+=max(dp[l],(long long)a[l]);
		}
	}
}

void bd2(long long x,long long w)
{
	long long i,sz=al[x].size(),l;
	
	vtd[x]=1;
	for(i=0;i<sz;i++)
	{
		l=al[x][i];
		if(!vtd[l])
		{
			dpl[x][i]=max(dp[l],(long long)a[l]);
			bd2(l,max(w+dp[x]-dpl[x][i],(long long)a[x]));
		}
		else
		{
			dpl[x][i]=w;
		}
	}
}

int main()
{
	long long i,j,k,l,sz,sm,z,c=0;
	string s;
	
	scanf("%lld",&n);
	for(i=0;i<n-1;i++)
	{
		scanf("%lld%lld",&k,&l);
		al[k].push_back(l);
		al[l].push_back(k);
		dpl[k].push_back(0);
		dpl[l].push_back(0);
	}
	cin>>s;
	for(i=1;i<=n;i++)
	{
		a[i]=s[i-1]-'0';
		c+=a[i];
	}
	z=2*(c>=2);
	bd(1);
	vtd.reset();
	bd2(1,0);
	for(i=1;i<=n;i++)
	{
		sm=-a[i];
		sz=dpl[i].size();
		for(j=0;j<sz;j++)
		{
			sm+=dpl[i][j];
		}
		z=max(z,max(sm,(long long)a[i]));
	}
	printf("%lld\n",z);
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |  scanf("%lld",&n);
      |  ~~~~~^~~~~~~~~~~
power.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |   scanf("%lld%lld",&k,&l);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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