Submission #427992

#	Time	Username	Problem	Language	Result	Execution time	Memory
427992		patrikpavic2	The Xana coup (BOI21_xanadu)	C++17	100 / 100	131 ms	21588 KiB

xanadu

#include <cstdio>
#include <cstring>
#include <vector>

#define PB push_back

using namespace std;

const int N = 1e5 + 500;
const int INF = 0x3f3f3f3f;

int n;
int dp[N][2][2], poc[N];
vector < int > v[N];

int f(int x, int lst, int ja, int par){
	if(dp[x][ja][par] != -1) return dp[x][ja][par];
	int cur0 = 0, cur1 = N;
	for(int y : v[x]){
		if(y == lst) continue;
		int pr0 = f(y, x, 0, ja);
		int pr1 = f(y, x, 1, ja);
		int nxt0 = min(cur0 + pr0, cur1 + pr1);
		int nxt1 = min(cur0 + pr1, cur1 + pr0);
		cur0 = nxt0, cur1 = nxt1;
	}
	return dp[x][ja][par] = ja + ((poc[x] ^ ja ^ par) ? cur1 : cur0);
}

int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int x, y; scanf("%d%d", &x, &y);
		v[x].PB(y), v[y].PB(x);
	}
	for(int i = 1;i <= n;i++)
		scanf("%d", poc + i);
	int sol = min(f(1, 1, 0, 0), f(1, 1, 1, 0));
	if(sol < N)	
		printf("%d\n", sol);
	else
		printf("impossible\n");
	return 0;
}

Compilation message (stderr)

xanadu.cpp: In function 'int main()':
xanadu.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
xanadu.cpp:34:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
xanadu.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d", poc + i);
      |   ~~~~~^~~~~~~~~~~~~~~

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