oj.uz

답안 #763247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763247 2023-06-22T07:10:44 Z nhphan0505 Power Plant (JOI20_power) C++17
0 / 100
 1 ms 340 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], dp[N], ans;
bool plant[N], visited[N];
char c;
vector<vector<ll>> adj;

void dfs(ll u){
	visited[u]=1;
	ll mx=0, ct=0, pos=0;
	for(auto v:adj[u]){
		if(!visited[v]){ 
			dfs(v);
			cnt[u]+=cnt[v];
			mx=max(mx, cnt[v]);
			if(cnt[v]) ++ct, pos=v;
		}
	}
	if(plant[u]) dp[u]=mx+1;
	if(ct>1) dp[u]=max(dp[u], cnt[u]);
	else dp[u]=max(dp[u], dp[pos]);
	cnt[u]=max(cnt[u]-plant[u], 1LL*plant[u]);
	// cout<<u<<" "<<dp[u]<<" "<<cnt[u]<<endl;
	ans=max(ans, dp[u]);
}

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<<ans;
    return 0;
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Halted 0 ms 0 KB -