oj.uz

답안 #309032

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
309032 2020-10-02T15:31:59 Z nhdtxdy Power Plant (JOI20_power) C++17
0 / 100
 4 ms 4992 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define Snape int main()
#define lumos ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define nox return 0
#define ll long long
#define pb push_back
#define Size(v) (int)v.size()
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define trav(a, x) for(auto &a : x)
using namespace std;
using namespace __gnu_pbds;

/*
"After all this time?"
"Always"
*/

const int nax = 2e5+5;
int n, dp[nax];
vector<int> g[nax];
string s;
int ans=0;

void dfs(int v, int p=0) {
	trav(c, g[v]) {
		if (c==p) continue;
		dfs(c, v);
	}
	int val = (s[v]=='1');
	dp[v]=max(dp[v],val);
	int sum=0;
	trav(c, g[v]) {
		if (c==p) continue;
		sum+=dp[c];
	}
	dp[v]=max(dp[v],sum-val);
}

void calc(int v, int p=0) {
	trav(c, g[v]) {
		if (c==p) continue;
		calc(c, v);
	}
	int val = (s[v]=='1');
	if (val==0) {
		int sum=0;
		trav(c, g[v]) {
			if (c==p) continue;
			sum+=dp[c];
		}
		ans=max(ans,sum);
	}
	else {
		int sum=0;
		trav(c, g[v]) {
			if (c == p) continue;
			ans=max(ans,dp[c]+1);
			sum+=dp[c];
		}
		ans=max(ans,sum-1);
	}
}

int main() {
	lumos;
	cin >> n;
	FOR (i,1,n-1) {
		int a,b; cin>>a>>b;
		g[a].pb(b);
		g[b].pb(a);
	}
	cin >> s; s = ' ' + s;
	dfs(1);
	calc(1);
	cout<<ans;
	nox;
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 4992 KB Output isn't correct
2 Halted 0 ms 0 KB -