oj.uz

답안 #763104

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763104 2023-06-22T03:41:15 Z nhphan0505 Power Plant (JOI20_power) C++17
0 / 100
 1 ms 212 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define gcd __gcd
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n, u, v, cnt[N], ans;
bool plant[N], visited[N];
char c;
vector<vector<ll>> adj;

ll dfs(ll u){
	visited[u]=1;
	ll res=0, sum=0;
	for(auto v:adj[u]){
		if(!visited[v]){ 
			dfs(v);
			cnt[u]+=cnt[v];
			res=max(res, cnt[v]);
		}
	}
	ans=max(ans, res+plant[u]);
	// cout<<u<<" "<<ans<<" "<<cnt[u]<<" ";
	cnt[u]=max(cnt[u]-plant[u], 1LL*plant[u]);
	// cout<<u<<" "<<cnt[u]<<endl;
	return res;
}

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>n;
	adj.assign(n+1, {});
	for(ll i=1; i<n; ++i){
		cin>>u>>v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	for(ll i=1; i<=n; ++i){
		cin>>c;
		plant[i]=c-'0';
		// if(plant[i]) cout<<i<<" ";
	}
	// cout<<endl;
	dfs(1);
	cout<<max(ans, cnt[1]+plant[1]);
    return 0;
}

Compilation message

power.cpp: In function 'll dfs(ll)':
power.cpp:20:12: warning: unused variable 'sum' [-Wunused-variable]
   20 |  ll res=0, sum=0;
      |            ^~~

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 41.0

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

Subtask #3
0.0 / 53.0

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