Submission #683903

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
683903	2023-01-19T15:29:56 Z	alvingogo	Power Plant (JOI20_power)	C++14	0 / 100	1 ms	336 KB

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(1,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

0.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	316 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	316 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	0 ms	324 KB	Output is correct
15	Incorrect	1 ms	212 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2

0.0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	316 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	316 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	0 ms	324 KB	Output is correct
15	Incorrect	1 ms	212 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	316 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	316 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	316 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	1 ms	316 KB	Output is correct
14	Correct	0 ms	324 KB	Output is correct
15	Incorrect	1 ms	212 KB	Output isn't correct
16	Halted	0 ms	0 KB	-