Submission #710841

#	Time	Username	Problem	Language	Result	Execution time	Memory
710841		Karpin	The Xana coup (BOI21_xanadu)	C++14	100 / 100	212 ms	23976 KiB

xanadu

#include <bits/stdc++.h>

using namespace std;


#define ll long long
#define vt vector
#define ar array


map<int, vt<int>> lines;

int L[1000005];

int dp[1000005][2][2];
int n;



void dfs(int cur, int prev){
    for(int s = 0; s < 2; s++){
        dp[cur][s][L[cur] ^ s] = s;
        dp[cur][s][L[cur] ^ s ^ 1] = n + 1;
    }

    for (int j : lines[cur]){
        if (j != prev){
            dfs(j, cur);
            for (int s = 0; s < 2; s++){
                int dp0 = dp[cur][s][0];
                int dp1 = dp[cur][s][1];
                dp[cur][s][0] = min(n + 1, min(dp0 + dp[j][0][s], dp1 + dp[j][1][s]));
                dp[cur][s][1] = min(n + 1, min(dp0 + dp[j][1][s], dp1 + dp[j][0][s]));
            }
        }
    }

}



void solve(){
		

    cin >> n;



    for (int i = 0; i < n - 1; i++){
        int a, b;

        cin >> a >> b;
        a--; b--;
        if (lines.find(a) == lines.end()) lines[a] = {};
        if (lines.find(b) == lines.end()) lines[b] = {};

        lines[a].push_back(b);
        lines[b].push_back(a);

    }

    

    for(int i = 0; i < n; i++){
        cin >> L[i];
    }


    dfs(0, -1);


    int res = min(dp[0][0][0], dp[0][1][0]);
    if (res > n) cout << "impossible" << endl;
    else cout << res << endl;



}

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int testcases = 1;

	// cin >> testcases;

	while(testcases--){
		solve();
	}

	return 0;

}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40
• Subtask 5: 30 / 30