oj.uz

답안 #1063378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1063378 2024-08-17T17:31:59 Z ThylOne Power Plant (JOI20_power) C++14
0 / 100
 2 ms 5176 KB 
//####################
//PowerPlant
//####################
#include<bits/stdc++.h>

using namespace std;
const int maxiN = 2*1e5;
bool isPowerPlant[maxiN];
vector<int> links[maxiN];
int dp[2][maxiN];
int solve(bool cm,int node,int dad=-1){
	if(dp[cm][node]!=-1)return dp[cm][node];
	int re = 0;
	if(isPowerPlant[node])re=1;
	int malus = (cm && isPowerPlant[node]?1:0);
	for(int v:links[node])if(v!=dad){
		re = max(re, solve(false,v,node) - malus);
	}
	int sum = 0;
	for(int v:links[node])if(v!=dad){
		sum += solve(true,v,node);
	}
	sum -=malus;
	 // le malus prcq ça va se faire péter

	return dp[cm][node] = max(re,sum) ;
}
signed main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
	for(int i = 1;i<n;i++){
		int a,b;cin>>a>>b;
		a--;
		b--;
		links[a].push_back(b);
		links[b].push_back(a);
	}
	fill(dp[0],dp[0]+n,-1);
	fill(dp[1],dp[1]+n,-1);
	string binary;cin>>binary;
	for(int i= 0;i<n;i++)isPowerPlant[i] = (binary[i]=='1');
	int ans = solve(0,0);
	for(int i = 0;i<n;i++){
		if(isPowerPlant[i]){
			for(int v:links[i])if(v!=i){
				ans = max(ans, 1+solve(1,v,i));
			}
		}
	}
	
	cout<<ans<<endl;
	return 0;
};

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 41.0

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

Subtask #3
0.0 / 53.0

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