Submission #1330880

#TimeUsernameProblemLanguageResultExecution timeMemory
1330880boclobanchatThe Xana coup (BOI21_xanadu)C++20
10 / 100
35 ms15672 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=1e9;
int dp[MAXN][2][2],pp[2][2],A[MAXN];
vector<int> ds[MAXN];
void dfs(int i,int pre)
{
	for(int a=0;a<2;a++) for(int b=0;b<2;b++) dp[i][a][b]=INF;
	dp[i][A[i]][0]=0;
	dp[i][1-A[i]][1]=1;
	for(auto v:ds[i]) if(v!=pre)
	{
		dfs(v,i);
		for(int a=0;a<2;a++) for(int b=0;b<2;b++) pp[a][b]=dp[i][a][b];
		dp[i][0][0]=min(pp[0][0]+dp[v][0][0],pp[1][0]+dp[v][0][1]);
		dp[i][0][1]=min(pp[0][1]+dp[v][1][0],pp[1][1]+dp[v][1][1]);
		dp[i][1][0]=min(pp[1][0]+dp[v][0][0],pp[0][0]+dp[v][0][1]);
		dp[i][1][1]=min(pp[1][1]+dp[v][1][0],pp[0][1]+dp[v][1][1]);
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	ds[l].push_back(r),ds[r].push_back(l);
	}
    for(int i=1;i<=n;i++) cin>>A[i];
    dfs(1,1);
    int ans=min(dp[1][0][0],dp[1][0][1]);
    if(ans>1e6) return cout<<"impossible",0;
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...