답안 #623822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623822	2022-08-06T14:51:31 Z	Arnch	Power Plant (JOI20_power)	C++17	100 / 100	163 ms	62400 KB

power

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int dp[N][2];
bool mark[N];
string s;
vector<int> adj[N];

void dfs(int x, int p = 0) {
	vector<int> cnt_0, cnt_1;
	for(auto j : adj[x]) {
		if(j == p) continue;
		dfs(j, x);
		cnt_0.push_back(dp[j][0]);
		cnt_1.push_back(dp[j][1]);
	}
	sort(All(cnt_0), greater<int>());
	sort(All(cnt_1), greater<int>());

	if(mark[x]) {
		dp[x][1] = 1;
		int val = 0;
		for(auto j : cnt_1) val += j;
		dp[x][1] = max(dp[x][1], val - 1);

		dp[x][0] = 1;
		if(Sz(cnt_1) > 0) dp[x][0] = max(dp[x][0], 1 + cnt_1[0]);
		if(Sz(cnt_0) > 0) dp[x][0] = max(dp[x][0], cnt_0[0]);
		val = 0;
		for(auto j : cnt_1) val += j;
		dp[x][0] = max(dp[x][0], val - 1);
		return;
	}
	int val = 0;
	for(auto j : cnt_1) val += j;
	dp[x][1] = val;

	if(Sz(cnt_0) > 0) dp[x][0] = cnt_0[0];
	val = 0;
	for(auto j : cnt_1) val += j;
	dp[x][0] = max(dp[x][0], val);
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	for(int i = 0; i < n - 1; i++) {
		int u, v; cin >>u >>v;
		adj[u].push_back(v), adj[v].push_back(u);
	}
	cin >>s;

	for(int i = 0; i < Sz(s); i++) mark[i + 1] = (s[i] == '1');

	dfs(1);

	cout<<dp[1][0];

    return 0;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	23720 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	13 ms	23708 KB	Output is correct
6	Correct	12 ms	23728 KB	Output is correct
7	Correct	13 ms	23740 KB	Output is correct
8	Correct	13 ms	23892 KB	Output is correct
9	Correct	13 ms	23816 KB	Output is correct
10	Correct	13 ms	23764 KB	Output is correct
11	Correct	12 ms	23796 KB	Output is correct
12	Correct	12 ms	23696 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23752 KB	Output is correct
17	Correct	13 ms	23764 KB	Output is correct
18	Correct	12 ms	23696 KB	Output is correct
19	Correct	12 ms	23812 KB	Output is correct
20	Correct	13 ms	23812 KB	Output is correct
21	Correct	12 ms	23716 KB	Output is correct

Subtask #2
41.0 / 41.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	23720 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	13 ms	23708 KB	Output is correct
6	Correct	12 ms	23728 KB	Output is correct
7	Correct	13 ms	23740 KB	Output is correct
8	Correct	13 ms	23892 KB	Output is correct
9	Correct	13 ms	23816 KB	Output is correct
10	Correct	13 ms	23764 KB	Output is correct
11	Correct	12 ms	23796 KB	Output is correct
12	Correct	12 ms	23696 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23752 KB	Output is correct
17	Correct	13 ms	23764 KB	Output is correct
18	Correct	12 ms	23696 KB	Output is correct
19	Correct	12 ms	23812 KB	Output is correct
20	Correct	13 ms	23812 KB	Output is correct
21	Correct	12 ms	23716 KB	Output is correct
22	Correct	14 ms	23924 KB	Output is correct
23	Correct	14 ms	24096 KB	Output is correct
24	Correct	13 ms	23908 KB	Output is correct
25	Correct	13 ms	23824 KB	Output is correct
26	Correct	13 ms	23892 KB	Output is correct
27	Correct	13 ms	23844 KB	Output is correct
28	Correct	14 ms	23880 KB	Output is correct
29	Correct	13 ms	24084 KB	Output is correct
30	Correct	13 ms	23980 KB	Output is correct
31	Correct	14 ms	23824 KB	Output is correct
32	Correct	13 ms	23876 KB	Output is correct
33	Correct	13 ms	23820 KB	Output is correct
34	Correct	13 ms	23912 KB	Output is correct
35	Correct	13 ms	23820 KB	Output is correct
36	Correct	13 ms	23860 KB	Output is correct
37	Correct	14 ms	23924 KB	Output is correct
38	Correct	13 ms	24020 KB	Output is correct
39	Correct	13 ms	23952 KB	Output is correct
40	Correct	13 ms	24008 KB	Output is correct
41	Correct	13 ms	23972 KB	Output is correct
42	Correct	13 ms	23892 KB	Output is correct
43	Correct	13 ms	23892 KB	Output is correct
44	Correct	13 ms	23876 KB	Output is correct
45	Correct	12 ms	23956 KB	Output is correct
46	Correct	13 ms	23952 KB	Output is correct
47	Correct	13 ms	23952 KB	Output is correct
48	Correct	13 ms	23992 KB	Output is correct
49	Correct	13 ms	24084 KB	Output is correct
50	Correct	13 ms	23924 KB	Output is correct
51	Correct	16 ms	23964 KB	Output is correct
52	Correct	13 ms	23892 KB	Output is correct
53	Correct	13 ms	23892 KB	Output is correct
54	Correct	13 ms	23944 KB	Output is correct
55	Correct	15 ms	23892 KB	Output is correct
56	Correct	13 ms	23892 KB	Output is correct
57	Correct	13 ms	24084 KB	Output is correct
58	Correct	13 ms	23892 KB	Output is correct
59	Correct	15 ms	23884 KB	Output is correct
60	Correct	13 ms	24056 KB	Output is correct
61	Correct	12 ms	23948 KB	Output is correct
62	Correct	13 ms	24000 KB	Output is correct
63	Correct	15 ms	23888 KB	Output is correct

Subtask #3
53.0 / 53.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	23720 KB	Output is correct
2	Correct	13 ms	23764 KB	Output is correct
3	Correct	12 ms	23764 KB	Output is correct
4	Correct	12 ms	23764 KB	Output is correct
5	Correct	13 ms	23708 KB	Output is correct
6	Correct	12 ms	23728 KB	Output is correct
7	Correct	13 ms	23740 KB	Output is correct
8	Correct	13 ms	23892 KB	Output is correct
9	Correct	13 ms	23816 KB	Output is correct
10	Correct	13 ms	23764 KB	Output is correct
11	Correct	12 ms	23796 KB	Output is correct
12	Correct	12 ms	23696 KB	Output is correct
13	Correct	12 ms	23764 KB	Output is correct
14	Correct	12 ms	23816 KB	Output is correct
15	Correct	13 ms	23764 KB	Output is correct
16	Correct	12 ms	23752 KB	Output is correct
17	Correct	13 ms	23764 KB	Output is correct
18	Correct	12 ms	23696 KB	Output is correct
19	Correct	12 ms	23812 KB	Output is correct
20	Correct	13 ms	23812 KB	Output is correct
21	Correct	12 ms	23716 KB	Output is correct
22	Correct	14 ms	23924 KB	Output is correct
23	Correct	14 ms	24096 KB	Output is correct
24	Correct	13 ms	23908 KB	Output is correct
25	Correct	13 ms	23824 KB	Output is correct
26	Correct	13 ms	23892 KB	Output is correct
27	Correct	13 ms	23844 KB	Output is correct
28	Correct	14 ms	23880 KB	Output is correct
29	Correct	13 ms	24084 KB	Output is correct
30	Correct	13 ms	23980 KB	Output is correct
31	Correct	14 ms	23824 KB	Output is correct
32	Correct	13 ms	23876 KB	Output is correct
33	Correct	13 ms	23820 KB	Output is correct
34	Correct	13 ms	23912 KB	Output is correct
35	Correct	13 ms	23820 KB	Output is correct
36	Correct	13 ms	23860 KB	Output is correct
37	Correct	14 ms	23924 KB	Output is correct
38	Correct	13 ms	24020 KB	Output is correct
39	Correct	13 ms	23952 KB	Output is correct
40	Correct	13 ms	24008 KB	Output is correct
41	Correct	13 ms	23972 KB	Output is correct
42	Correct	13 ms	23892 KB	Output is correct
43	Correct	13 ms	23892 KB	Output is correct
44	Correct	13 ms	23876 KB	Output is correct
45	Correct	12 ms	23956 KB	Output is correct
46	Correct	13 ms	23952 KB	Output is correct
47	Correct	13 ms	23952 KB	Output is correct
48	Correct	13 ms	23992 KB	Output is correct
49	Correct	13 ms	24084 KB	Output is correct
50	Correct	13 ms	23924 KB	Output is correct
51	Correct	16 ms	23964 KB	Output is correct
52	Correct	13 ms	23892 KB	Output is correct
53	Correct	13 ms	23892 KB	Output is correct
54	Correct	13 ms	23944 KB	Output is correct
55	Correct	15 ms	23892 KB	Output is correct
56	Correct	13 ms	23892 KB	Output is correct
57	Correct	13 ms	24084 KB	Output is correct
58	Correct	13 ms	23892 KB	Output is correct
59	Correct	15 ms	23884 KB	Output is correct
60	Correct	13 ms	24056 KB	Output is correct
61	Correct	12 ms	23948 KB	Output is correct
62	Correct	13 ms	24000 KB	Output is correct
63	Correct	15 ms	23888 KB	Output is correct
64	Correct	155 ms	35004 KB	Output is correct
65	Correct	148 ms	34968 KB	Output is correct
66	Correct	151 ms	35004 KB	Output is correct
67	Correct	140 ms	34936 KB	Output is correct
68	Correct	150 ms	34988 KB	Output is correct
69	Correct	140 ms	34984 KB	Output is correct
70	Correct	143 ms	34972 KB	Output is correct
71	Correct	141 ms	34968 KB	Output is correct
72	Correct	147 ms	34924 KB	Output is correct
73	Correct	157 ms	60300 KB	Output is correct
74	Correct	163 ms	60148 KB	Output is correct
75	Correct	142 ms	34820 KB	Output is correct
76	Correct	151 ms	34768 KB	Output is correct
77	Correct	139 ms	34832 KB	Output is correct
78	Correct	149 ms	34868 KB	Output is correct
79	Correct	140 ms	34868 KB	Output is correct
80	Correct	159 ms	34776 KB	Output is correct
81	Correct	121 ms	36348 KB	Output is correct
82	Correct	135 ms	35508 KB	Output is correct
83	Correct	151 ms	46136 KB	Output is correct
84	Correct	163 ms	50848 KB	Output is correct
85	Correct	152 ms	50088 KB	Output is correct
86	Correct	144 ms	38060 KB	Output is correct
87	Correct	153 ms	36676 KB	Output is correct
88	Correct	150 ms	36852 KB	Output is correct
89	Correct	130 ms	36804 KB	Output is correct
90	Correct	131 ms	36472 KB	Output is correct
91	Correct	146 ms	36840 KB	Output is correct
92	Correct	133 ms	37480 KB	Output is correct
93	Correct	127 ms	43096 KB	Output is correct
94	Correct	131 ms	46212 KB	Output is correct
95	Correct	126 ms	43868 KB	Output is correct
96	Correct	138 ms	39892 KB	Output is correct
97	Correct	127 ms	36632 KB	Output is correct
98	Correct	120 ms	35620 KB	Output is correct
99	Correct	131 ms	35316 KB	Output is correct
100	Correct	127 ms	41996 KB	Output is correct
101	Correct	130 ms	37624 KB	Output is correct
102	Correct	125 ms	35968 KB	Output is correct
103	Correct	130 ms	35628 KB	Output is correct
104	Correct	90 ms	38336 KB	Output is correct
105	Correct	159 ms	53868 KB	Output is correct
106	Correct	88 ms	38144 KB	Output is correct
107	Correct	86 ms	38128 KB	Output is correct
108	Correct	157 ms	61800 KB	Output is correct
109	Correct	95 ms	38332 KB	Output is correct
110	Correct	160 ms	62400 KB	Output is correct
111	Correct	134 ms	34852 KB	Output is correct

답안 #623822

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 41.0 / 41.0

Subtask #3 53.0 / 53.0

Subtask #1
6.0 / 6.0

Subtask #2
41.0 / 41.0

Subtask #3
53.0 / 53.0