Submission #1211600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211600		_Temirhan	Power Plant (JOI20_power)	C++20	0 / 100	2 ms	4928 KiB

power

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>  
#include <ext/pb_ds/tree_policy.hpp>  
 
using namespace std;
using namespace __gnu_pbds;
 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define int long long
#define sz(x) x.size()
#define F first
#define S second
#define pb push_back
#define nl '\n';
 
void Debug()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif
}
 
const int N = 2e5 + 1;
const int inf = 1e9 + 1;
const int INF = 1e18;
const int mod = 1e9 + 7;
int T = 1, n, p[N], c[N], cnt, ch, ans, pp[N];
string s;
vector< int >g[N];

void DFS( int v, int pr )
{
	c[v] = p[v];
	int Cnt = 0;
	for( int to: g[v] )
		if( to != pr )
		{
			DFS(to, v);
			Cnt += c[to];
			p[v] += p[to];
		}
	// cout << v << ' ' << c[v] << ' ' << Cnt << '\n';
	c[v] = max(c[v], Cnt - c[v]);
}

void dfs( int v, int pr )
{
	int res = 0;
	for( int to: g[v] )
		if( to != pr )
		{
			dfs(to, v);
			res += c[to];
		}
	if( pp[v] )
		return; 
	ans = max(ans, res);
	if( v != 1 && p[1] - p[v] > 0 )
		++res;
	ans = max(ans, res);
	// cout << v << ' ' << res << '\n';
}

signed main()
{
	// Debug();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >>n;
	for( int i = 1, u, v; i < n; ++i )
	{
		cin >>u >>v;
		g[u].pb( v );
		g[v].pb( u );
	}
	cin >>s;
	for( int i = 0; i < n; ++i )
		if( s[i] == '1' )
		{
			++cnt;
			p[i + 1] = 1;
			pp[i + 1] = 1;
		}
	DFS(1, 0);
	dfs(1, 0);
	cout <<ans;
}

Compilation message (stderr)

power.cpp: In function 'void Debug()':
power.cpp:19:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |                 freopen("input.txt", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
power.cpp:20:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |                 freopen("output.txt", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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