Submission #731704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
731704	2023-04-27T20:13:13 Z	NintsiChkhaidze	The Xana coup (BOI21_xanadu)	C++17	100 / 100	125 ms	25096 KB

xanadu

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
 
const int N = 1e5 + 5,inf=1e9;
vector <int> v[N];
int c[N];
int dp[4][N][4];

void dfs(int x,int par){
	int valblack = 0,valblack0 = inf,parblack = 1;
	int valwhite = 0,valwhite0 = inf,parwhite = 0;

	for (int to: v[x]){
		if (to == par) continue;
		dfs(to,x);
		//black
		valblack += min(dp[0][to][1],dp[0][to][0]);
		if (min(dp[0][to][1],dp[0][to][0]) == dp[0][to][1]) parblack++;
		valblack0 = min(valblack0, abs(dp[0][to][1] - dp[0][to][0]));

		//white
		valwhite += min(dp[1][to][1],dp[1][to][0]);
		if (min(dp[1][to][1],dp[1][to][0]) == dp[1][to][1]) parwhite++;
		valwhite0 = min(valwhite0, abs(dp[1][to][1] - dp[1][to][0]));
	}

	parblack%=2;
	parwhite%=2;

	int color = 1 - c[x];
	int oppcolor = c[x];

	//x-ზე ოპერაციას ვაკეთებთ
	if (parblack){
		dp[oppcolor][x][1] = min(dp[oppcolor][x][1],valblack + 1);
		dp[color][x][1] = min(dp[color][x][1],valblack + valblack0 + 1);
	}else{
		dp[color][x][1] = min(dp[color][x][1],valblack + 1);
		dp[oppcolor][x][1] = min(dp[oppcolor][x][1],valblack + valblack0 + 1);
	}

	//x-ზე ოპერაციას არ ვაკეთებთ
	if (parwhite){
		dp[oppcolor][x][0] = min(dp[oppcolor][x][0],valwhite);
		dp[color][x][0] = min(dp[color][x][0],valwhite + valwhite0);
	}else{
		dp[color][x][0] = min(dp[color][x][0],valwhite);
		dp[oppcolor][x][0] = min(dp[oppcolor][x][0],valwhite + valwhite0);
	}
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n;
	cin>>n;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}

	for (int i = 1; i <= n; i++)
		cin>>c[i]; //c[i] = 0 -> i-წვერო თეთრი ფერია

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 2; j++)
			for (int p = 0; p < 2; p++)
			dp[p][i][j] = inf;

	//j ნიშნავს i წვეროზე ოპერაციას ვაკეთებ თუ არა
	dfs(1,1);
	int ans = min(dp[1][1][1],dp[1][1][0]);
	if (ans == inf) cout<<"impossible";
	else cout<<ans;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	3 ms	2644 KB	Output is correct

Subtask #2
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	3 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2644 KB	Output is correct
9	Correct	2 ms	2644 KB	Output is correct
10	Correct	2 ms	2644 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	2 ms	2664 KB	Output is correct
13	Correct	3 ms	2644 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	2 ms	2680 KB	Output is correct
16	Correct	2 ms	2644 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	23648 KB	Output is correct
2	Correct	61 ms	24684 KB	Output is correct
3	Correct	56 ms	25076 KB	Output is correct

Subtask #4
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	23688 KB	Output is correct
2	Correct	57 ms	24724 KB	Output is correct
3	Correct	57 ms	25052 KB	Output is correct
4	Correct	60 ms	13684 KB	Output is correct
5	Correct	62 ms	14760 KB	Output is correct
6	Correct	65 ms	14984 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	16 ms	6740 KB	Output is correct
9	Correct	63 ms	14540 KB	Output is correct
10	Correct	62 ms	14796 KB	Output is correct
11	Correct	66 ms	15204 KB	Output is correct
12	Correct	105 ms	15560 KB	Output is correct
13	Correct	102 ms	14572 KB	Output is correct
14	Correct	61 ms	15340 KB	Output is correct

Subtask #5
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2644 KB	Output is correct
2	Correct	1 ms	2644 KB	Output is correct
3	Correct	1 ms	2644 KB	Output is correct
4	Correct	2 ms	2644 KB	Output is correct
5	Correct	3 ms	2644 KB	Output is correct
6	Correct	2 ms	2644 KB	Output is correct
7	Correct	2 ms	2644 KB	Output is correct
8	Correct	2 ms	2644 KB	Output is correct
9	Correct	2 ms	2644 KB	Output is correct
10	Correct	2 ms	2644 KB	Output is correct
11	Correct	2 ms	2644 KB	Output is correct
12	Correct	2 ms	2664 KB	Output is correct
13	Correct	3 ms	2644 KB	Output is correct
14	Correct	2 ms	2644 KB	Output is correct
15	Correct	2 ms	2680 KB	Output is correct
16	Correct	2 ms	2644 KB	Output is correct
17	Correct	51 ms	23648 KB	Output is correct
18	Correct	61 ms	24684 KB	Output is correct
19	Correct	56 ms	25076 KB	Output is correct
20	Correct	51 ms	23688 KB	Output is correct
21	Correct	57 ms	24724 KB	Output is correct
22	Correct	57 ms	25052 KB	Output is correct
23	Correct	60 ms	13684 KB	Output is correct
24	Correct	62 ms	14760 KB	Output is correct
25	Correct	65 ms	14984 KB	Output is correct
26	Correct	2 ms	2644 KB	Output is correct
27	Correct	16 ms	6740 KB	Output is correct
28	Correct	63 ms	14540 KB	Output is correct
29	Correct	62 ms	14796 KB	Output is correct
30	Correct	66 ms	15204 KB	Output is correct
31	Correct	105 ms	15560 KB	Output is correct
32	Correct	102 ms	14572 KB	Output is correct
33	Correct	61 ms	15340 KB	Output is correct
34	Correct	2 ms	2684 KB	Output is correct
35	Correct	2 ms	2688 KB	Output is correct
36	Correct	2 ms	2644 KB	Output is correct
37	Correct	2 ms	2644 KB	Output is correct
38	Correct	2 ms	2644 KB	Output is correct
39	Correct	2 ms	2680 KB	Output is correct
40	Correct	2 ms	2644 KB	Output is correct
41	Correct	2 ms	2648 KB	Output is correct
42	Correct	3 ms	2680 KB	Output is correct
43	Correct	2 ms	2644 KB	Output is correct
44	Correct	2 ms	2644 KB	Output is correct
45	Correct	51 ms	24908 KB	Output is correct
46	Correct	53 ms	24756 KB	Output is correct
47	Correct	59 ms	25096 KB	Output is correct
48	Correct	62 ms	13696 KB	Output is correct
49	Correct	64 ms	14776 KB	Output is correct
50	Correct	67 ms	14964 KB	Output is correct
51	Correct	2 ms	2644 KB	Output is correct
52	Correct	17 ms	6696 KB	Output is correct
53	Correct	106 ms	14552 KB	Output is correct
54	Correct	125 ms	14796 KB	Output is correct
55	Correct	68 ms	15188 KB	Output is correct
56	Correct	62 ms	15628 KB	Output is correct
57	Correct	64 ms	14580 KB	Output is correct
58	Correct	62 ms	15364 KB	Output is correct
59	Correct	16 ms	6668 KB	Output is correct
60	Correct	68 ms	13392 KB	Output is correct
61	Correct	80 ms	14460 KB	Output is correct
62	Correct	77 ms	14788 KB	Output is correct
63	Correct	75 ms	14708 KB	Output is correct
64	Correct	69 ms	14760 KB	Output is correct
65	Correct	56 ms	15156 KB	Output is correct
66	Correct	57 ms	15180 KB	Output is correct
67	Correct	87 ms	14932 KB	Output is correct
68	Correct	46 ms	14912 KB	Output is correct
69	Correct	46 ms	14892 KB	Output is correct
70	Correct	51 ms	14864 KB	Output is correct

Submission #731704

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 15.0 / 15.0

Subtask #3 10.0 / 10.0

Subtask #4 40.0 / 40.0

Subtask #5 30.0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
15.0 / 15.0

Subtask #3
10.0 / 10.0

Subtask #4
40.0 / 40.0

Subtask #5
30.0 / 30.0