Submission #1280153

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280153		Bui_Quoc_Cuong	The Xana coup (BOI21_xanadu)	C++20	100 / 100	70 ms	27012 KiB

xanadu

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for (int i = a; i >= (int)b; i--)
#define ll long long
const int maxn = 2e5 + 20;

template <class A, class B>
bool minimize (A &a, const B b)
{
	if (a > b)
	{
		a = b;
		return true;
	} return false;
}

int n;
vector <int> g[maxn];
int a[maxn];
int dp[maxn][3][3], f[maxn][3][3];

void dfs (int u, int p = - 1)
{
	vector <int> node_son;
	node_son.push_back(0);
	for (int &v : g[u]) if (v != p)
	{
		dfs(v, u);
		node_son.push_back(v);
	}	
	for (int j = 0; j <= 1; j++) for (int t = 0; t <= 1; t++)
		dp[u][j][t] = 1e9;	
	for (int i = 0; i < (int)node_son.size() + 4; i++)
		for (int j = 0; j <= 1; j++) f[i][j][0] = f[i][j][1] = 1e9;
	
	f[0][a[u]][0] = 0;
	f[0][a[u] ^ 1][1] = 1;

	for (int i = 0; i < (int)node_son.size() - 1; i++)
	{
		int v = node_son[i + 1];
		for (int j = 0; j <= 1; j++)
		{
			// calc for dp[u][0 / 1][0]
			minimize (f[i + 1][j][0], dp[v][0][0] + f[i][j][0]);
			minimize (f[i + 1][j ^ 1][0], dp[v][0][1] + f[i][j][0]);

			// calc for dp[u][0 / 1][1]
			minimize (f[i + 1][j][1], dp[v][1][0] + f[i][j][1]);
			minimize (f[i + 1][j ^ 1][1], dp[v][1][1] + f[i][j][1]);
		}
	}	

	for (int j = 0; j <= 1; j++)
	{
		dp[u][j][0] = f[node_son.size() - 1][j][0];
		dp[u][j][1] = f[node_son.size() - 1][j][1];
	}
}

signed main () 
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #define kieuoanh "kieuoanh"
    if (fopen(kieuoanh".inp", "r")) 
    {
        freopen(kieuoanh".inp", "r", stdin); 
        freopen(kieuoanh".out", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i < n; i++)
    {
    	int u, v; cin >> u >> v;
    	g[u].push_back(v); g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
    	cin >> a[i];
    dfs(1);
    int ans = min(dp[1][0][0], dp[1][0][1]);

    // for (int u = 1; u <= n; u++)
    // {
    	// cout << dp[u][0][0] << " " << dp[u][1][0] << " " << dp[u][0][1] << " " << dp[u][1][1] << "\n";
    // }
// 
    if (ans >= 1e9) cout << "impossible";
    else cout << ans;
    return 0;   
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen(kieuoanh".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
xanadu.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         freopen(kieuoanh".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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