Submission #683904

#	Time	Username	Problem	Language	Result	Execution time	Memory
683904		alvingogo	Power Plant (JOI20_power)	C++14	100 / 100	195 ms	24940 KiB

power

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct no{
	vector<int> ch;
	int t;
	int dp=0;	
};
vector<no> v;
int ans=1;
void dfs(int r,int f){
	for(auto h:v[r].ch){
		if(h!=f){
			dfs(h,r);
			v[r].dp+=v[h].dp;
		}
	}
	if(v[r].t==1){
		v[r].dp=max(v[r].dp-1,1);
	}
}
void dfs2(int r,int f,int x){
	v[r].dp+=x;
	ans=max(ans,v[r].dp);
	for(auto h:v[r].ch){
		if(h!=f){
			dfs2(h,r,max(v[r].t,v[r].dp-v[h].dp));
		}
	}
}
int main(){
    AquA;
	int n;
	cin >> n;
	v.resize(n);
	for(int i=1;i<n;i++){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		v[a].ch.push_back(b);
		v[b].ch.push_back(a);
	}
	string s;
	cin >> s;
	for(int i=0;i<n;i++){
		v[i].t=s[i]-'0';
	}
	dfs(0,0);
	dfs2(0,0,0);
	cout << ans << "\n";
    return 0;
}

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