Submission #763724

#	Time	Username	Problem	Language	Result	Execution time	Memory
763724		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	115 ms	28500 KiB

power

// Cu code roi se AC
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⡄⢠⡄⣠⠤⢤⡀⣤⠀⢠⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡏⠀⣿⠀⢨⡇⣿⠀⢸⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠁⠀⠈⠉⠉⠀⠈⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⢠⠤⣄⢠⡄⠀⣤⢀⣠⢤⡀⢠⡄⠀⡄⢠⡀⠀⢠⣤⣤⡀⠀⠀⠀⠀
// ⠀⠀⠀⠀⣙⠲⢦⢸⡗⠒⣿⢸⡁⠀⣿⢸⡇⠀⡇⢸⡇⠀⢸⡇⠀⡷⠀⠀⠀⠀
// ⠀⠀⠀⠀⠈⠛⠋⠈⠃⠀⠋⠀⠙⠛⠁⠀⠙⠛⠁⠘⠛⠛⠘⠛⠋⠁⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⢀⡀⢀⠀⡀⠀⠀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡷⣯⠀⢸⠀⡇⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠃⠈⠓⠘⠀⠛⠒⠂⠛⠒⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⣀⠀⢀⡀⢀⣀⡀⠀⡀⠀⣀⢀⣀⣀⡀⢀⣀⣀⠀⣀⣀⡀⣀⠀⠀⢀⣀⣀⠀
// ⠀⠘⢷⠏⢰⡏⠀⢹⠄⡇⠀⣿⢸⣧⢤⡇⠘⠦⣬⡀⡧⠤⠄⣿⠀⠀⢸⠤⠄⠀
// ⠀⠀⠘⠀⠀⠛⠒⠋⠀⠛⠒⠋⠘⠃⠀⠓⠘⠲⠚⠁⠓⠒⠂⠛⠒⠒⠘⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⡀⠀⢀⠀⢀⣀⠀⢀⠀⢀⠀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⡿⢆⣸⢠⡏⠉⢹⡈⣇⡼⣇⣼⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠇⠈⠿⠀⠳⠶⠞⠀⠹⠇⠸⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⠏⠄⠄⠄⠄⠄⠄⠄⠄⠙⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⠄⠄⢀⣀⣀⣀⡀⠄⢀⣠⡔⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣰⢿⣿⣿⣿⣿⣿⣿⣷⡆⢠⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⡏⣻⣟⣿⣿⡿⣟⣛⣿⡃⢸⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣧⣿⣾⣿⣷⣿⣷⣿⣿⣿⣷⣽⣹⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⡟⣟⣿⣿⠺⣟⣻⣿⣿⣿⡏⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⡝⠻⠵⠿⠿⢿⣿⣿⢳⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣯⣧⠈⣛⣛⣿⣿⡿⣡⣞⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡧⠄⠙⠛⠛⢁⣴⣿⣿⣷⣿⢿⣿⣿⣿⣿⣿⣿⣿
// ⣿⣿⣿⣿⣿⣿⡿⠟⠉⠄⠄⢠⠄⣀⣠⣾⣿⣿⡿⠟⠁⠄⠈⠛⢿⣿⣿⣿⣿
// ⣿⣿⣿⣿⡟⠉⠄⠄⢀⠠⠐⠒⠐⠾⠿⢟⠋⠁⠄⢀⣀⠠⠐⠄⠂⠈⠻⢿⣿
// ⣿⣿⣿⠋⠁⠄⢀⡈⠄⠄⠄⠄⠄⠄⠄⠄⠁⠒⠉⠄⢠⣶⠄⠄⠄⠄⠄⠈⠫
// ⣿⣿⡟⠄⢔⠆⡀⠄⠈⢀⠄⠄⠄⠄⠄⠄⠄⢄⡀⠄⠈⡐⢠⠒⠄⠄⠄⠄⢀
// ⣿⣿⠁⡀⠄⠄⢇⠄⠄⢈⠆⠄⠄⢀⠔⠉⠁⠉⠉⠣⣖⠉⡂⡔⠂⠄⢀⠔⠁
// ⣿⡿⠄⠄⠄⠄⢰⠹⣗⣺⠤⠄⠰⡎⠄⠄⠄⠄⠄⠄⠘⢯⡶⢟⡠⠰⠄⠄

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using type=ll;
#define taskname "table"
// for Orac
#define tasknamein "table"
#define tasknameout "table"
#define fi first
#define se second
#define sz(v) ((type)(v).size())
#define all(v) (v).begin(), (v).end()
typedef pair<type, type> ii;      
typedef vector<ii> vii;      
typedef vector<type> vi;   
typedef vector<vector<type>> vvi;
//for FFT     
using cd = complex<double>;
const double PI = acos(-1);
const type MN=2e5+10;
const type oo=1e18;
const type llmax=0x3f3f3f3f3f3f;

type n, a, b, dp[MN], ans[MN];
vi AdjList[MN];
string s;

void dfs(type u, type v) {
	dp[u]-=(s[u]-'0');
	type Max=0;
	for(int i:AdjList[u]) {
		if(i!=v) {
			dfs(i, u);
			dp[u]+=dp[i];
			ans[u]=max(ans[u], dp[i]+(s[u]-'0'));
		}
	}
	dp[u]=max(dp[u], (type)(s[u]-'0'));
	ans[u]=max(ans[u], dp[u]);
}

void read() {
	cin >> n;
	for(int i=1; i<=n-1; i++) {
		cin >> a >> b;
		AdjList[a].push_back(b);
		AdjList[b].push_back(a);
	}
	cin >> s;
}

void sol(){
	s='#'+s;
	dfs(1, 1);
	cout << *max_element(ans + 1, ans + n + 1);
}

signed main() {
    //freopen(taskname".inp", "r", stdin);
    //freopen(taskname".out", "w", stdout);
    //for Orac
    /*
    ifstream in("tasknamein.txt");
    ofstream out("tasknameout.txt");
    */
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    type t;
    // cin >> t;
    t=1;
    while(t--) {
    	read();  
    	sol();
    	cout << endl;
    }  
}

Compilation message (stderr)

power.cpp: In function 'void dfs(type, type)':
power.cpp:64:7: warning: unused variable 'Max' [-Wunused-variable]
   64 |  type Max=0;
      |       ^~~

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