# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
293186 | 2020-09-07T17:50:25 Z | CaroLinda | Power Plant (JOI20_power) | C++14 | 216 ms | 27148 KB |
#include <bits/stdc++.h> #define pb push_back #define ll long long #define pii pair<int,int> #define mk make_pair #define all(x) x.begin(),x.end() #define ff first #define ss second #define debug printf #define lp(i,a,b) for(int i = a ; i < b ; i++ ) #define sz(x) (int)(x.size()) const int MAXN = 2e5+10 ; using namespace std ; int N ; int dp[MAXN][2] ; vector<int> adj[MAXN] ; bool isPower[MAXN] ; char str[MAXN] ; void dfs(int x, int dad) { int mx[2] = {0,0} ; int soma1 = 0 ; for(auto e : adj[x] ) { if(e == dad) continue ; dfs(e,x) ; lp(i,0,2) mx[i] = max(mx[i] , dp[e][i]) ; soma1 += dp[e][1] ; } if(!isPower[x]) { dp[x][0] = max( soma1, mx[0] ) ; dp[x][1] = soma1 ; } else { dp[x][0] = max( mx[1] + 1 , soma1 - 1 ) ; dp[x][0] = max( dp[x][0] , mx[0] ) ; dp[x][1] = max( 1 , soma1 - 1 ) ; } } int main() { scanf("%d", &N) ; for(int i = 1 , u ,v ; i < N ; i++ ) { scanf("%d%d", &u, &v ) ; adj[u].pb(v) ; adj[v].pb(u) ; } scanf("%s", str ) ; lp(i,0,N) isPower[i+1] = ( str[i] == '1' ) ; dfs(1,-1) ; printf("%d\n" , dp[1][0]) ; } /* 6 2 1 2 3 2 4 2 5 2 6 111111 6 2 1 2 3 2 4 2 5 2 6 011111 5 1 2 2 3 3 4 4 5 11100 6 2 1 2 3 2 4 2 5 2 6 010101 16 14 10 14 13 14 16 13 11 11 12 13 15 13 5 16 3 16 8 16 1 12 4 4 7 10 2 7 6 16 9 1111111111111111 10 1 4 2 4 3 4 4 5 5 7 7 6 7 8 7 9 7 10 1111111111 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 3 ms | 4992 KB | Output is correct |
3 | Correct | 4 ms | 5024 KB | Output is correct |
4 | Correct | 4 ms | 4992 KB | Output is correct |
5 | Correct | 3 ms | 4992 KB | Output is correct |
6 | Correct | 3 ms | 4992 KB | Output is correct |
7 | Correct | 3 ms | 4992 KB | Output is correct |
8 | Correct | 3 ms | 4992 KB | Output is correct |
9 | Correct | 4 ms | 4992 KB | Output is correct |
10 | Correct | 3 ms | 4992 KB | Output is correct |
11 | Correct | 4 ms | 4992 KB | Output is correct |
12 | Correct | 3 ms | 4992 KB | Output is correct |
13 | Correct | 3 ms | 4992 KB | Output is correct |
14 | Correct | 3 ms | 4992 KB | Output is correct |
15 | Correct | 4 ms | 4992 KB | Output is correct |
16 | Correct | 3 ms | 4992 KB | Output is correct |
17 | Correct | 3 ms | 5024 KB | Output is correct |
18 | Correct | 3 ms | 4992 KB | Output is correct |
19 | Correct | 4 ms | 5120 KB | Output is correct |
20 | Correct | 4 ms | 4992 KB | Output is correct |
21 | Correct | 3 ms | 4992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 3 ms | 4992 KB | Output is correct |
3 | Correct | 4 ms | 5024 KB | Output is correct |
4 | Correct | 4 ms | 4992 KB | Output is correct |
5 | Correct | 3 ms | 4992 KB | Output is correct |
6 | Correct | 3 ms | 4992 KB | Output is correct |
7 | Correct | 3 ms | 4992 KB | Output is correct |
8 | Correct | 3 ms | 4992 KB | Output is correct |
9 | Correct | 4 ms | 4992 KB | Output is correct |
10 | Correct | 3 ms | 4992 KB | Output is correct |
11 | Correct | 4 ms | 4992 KB | Output is correct |
12 | Correct | 3 ms | 4992 KB | Output is correct |
13 | Correct | 3 ms | 4992 KB | Output is correct |
14 | Correct | 3 ms | 4992 KB | Output is correct |
15 | Correct | 4 ms | 4992 KB | Output is correct |
16 | Correct | 3 ms | 4992 KB | Output is correct |
17 | Correct | 3 ms | 5024 KB | Output is correct |
18 | Correct | 3 ms | 4992 KB | Output is correct |
19 | Correct | 4 ms | 5120 KB | Output is correct |
20 | Correct | 4 ms | 4992 KB | Output is correct |
21 | Correct | 3 ms | 4992 KB | Output is correct |
22 | Correct | 4 ms | 5120 KB | Output is correct |
23 | Correct | 4 ms | 5120 KB | Output is correct |
24 | Correct | 4 ms | 5120 KB | Output is correct |
25 | Correct | 4 ms | 5120 KB | Output is correct |
26 | Correct | 4 ms | 5120 KB | Output is correct |
27 | Correct | 4 ms | 5120 KB | Output is correct |
28 | Correct | 4 ms | 5120 KB | Output is correct |
29 | Correct | 5 ms | 5248 KB | Output is correct |
30 | Correct | 4 ms | 5248 KB | Output is correct |
31 | Correct | 5 ms | 5120 KB | Output is correct |
32 | Correct | 4 ms | 5120 KB | Output is correct |
33 | Correct | 4 ms | 5120 KB | Output is correct |
34 | Correct | 5 ms | 5120 KB | Output is correct |
35 | Correct | 4 ms | 5120 KB | Output is correct |
36 | Correct | 5 ms | 5120 KB | Output is correct |
37 | Correct | 4 ms | 5120 KB | Output is correct |
38 | Correct | 5 ms | 5120 KB | Output is correct |
39 | Correct | 5 ms | 5248 KB | Output is correct |
40 | Correct | 4 ms | 5120 KB | Output is correct |
41 | Correct | 5 ms | 5120 KB | Output is correct |
42 | Correct | 4 ms | 5120 KB | Output is correct |
43 | Correct | 4 ms | 5120 KB | Output is correct |
44 | Correct | 4 ms | 5120 KB | Output is correct |
45 | Correct | 4 ms | 5120 KB | Output is correct |
46 | Correct | 4 ms | 5120 KB | Output is correct |
47 | Correct | 4 ms | 5120 KB | Output is correct |
48 | Correct | 4 ms | 5248 KB | Output is correct |
49 | Correct | 4 ms | 5248 KB | Output is correct |
50 | Correct | 4 ms | 5120 KB | Output is correct |
51 | Correct | 4 ms | 5120 KB | Output is correct |
52 | Correct | 4 ms | 5120 KB | Output is correct |
53 | Correct | 4 ms | 5120 KB | Output is correct |
54 | Correct | 4 ms | 5120 KB | Output is correct |
55 | Correct | 4 ms | 5120 KB | Output is correct |
56 | Correct | 4 ms | 5120 KB | Output is correct |
57 | Correct | 5 ms | 5248 KB | Output is correct |
58 | Correct | 4 ms | 5120 KB | Output is correct |
59 | Correct | 4 ms | 5120 KB | Output is correct |
60 | Correct | 4 ms | 5248 KB | Output is correct |
61 | Correct | 4 ms | 5120 KB | Output is correct |
62 | Correct | 4 ms | 5248 KB | Output is correct |
63 | Correct | 4 ms | 5120 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 4992 KB | Output is correct |
2 | Correct | 3 ms | 4992 KB | Output is correct |
3 | Correct | 4 ms | 5024 KB | Output is correct |
4 | Correct | 4 ms | 4992 KB | Output is correct |
5 | Correct | 3 ms | 4992 KB | Output is correct |
6 | Correct | 3 ms | 4992 KB | Output is correct |
7 | Correct | 3 ms | 4992 KB | Output is correct |
8 | Correct | 3 ms | 4992 KB | Output is correct |
9 | Correct | 4 ms | 4992 KB | Output is correct |
10 | Correct | 3 ms | 4992 KB | Output is correct |
11 | Correct | 4 ms | 4992 KB | Output is correct |
12 | Correct | 3 ms | 4992 KB | Output is correct |
13 | Correct | 3 ms | 4992 KB | Output is correct |
14 | Correct | 3 ms | 4992 KB | Output is correct |
15 | Correct | 4 ms | 4992 KB | Output is correct |
16 | Correct | 3 ms | 4992 KB | Output is correct |
17 | Correct | 3 ms | 5024 KB | Output is correct |
18 | Correct | 3 ms | 4992 KB | Output is correct |
19 | Correct | 4 ms | 5120 KB | Output is correct |
20 | Correct | 4 ms | 4992 KB | Output is correct |
21 | Correct | 3 ms | 4992 KB | Output is correct |
22 | Correct | 4 ms | 5120 KB | Output is correct |
23 | Correct | 4 ms | 5120 KB | Output is correct |
24 | Correct | 4 ms | 5120 KB | Output is correct |
25 | Correct | 4 ms | 5120 KB | Output is correct |
26 | Correct | 4 ms | 5120 KB | Output is correct |
27 | Correct | 4 ms | 5120 KB | Output is correct |
28 | Correct | 4 ms | 5120 KB | Output is correct |
29 | Correct | 5 ms | 5248 KB | Output is correct |
30 | Correct | 4 ms | 5248 KB | Output is correct |
31 | Correct | 5 ms | 5120 KB | Output is correct |
32 | Correct | 4 ms | 5120 KB | Output is correct |
33 | Correct | 4 ms | 5120 KB | Output is correct |
34 | Correct | 5 ms | 5120 KB | Output is correct |
35 | Correct | 4 ms | 5120 KB | Output is correct |
36 | Correct | 5 ms | 5120 KB | Output is correct |
37 | Correct | 4 ms | 5120 KB | Output is correct |
38 | Correct | 5 ms | 5120 KB | Output is correct |
39 | Correct | 5 ms | 5248 KB | Output is correct |
40 | Correct | 4 ms | 5120 KB | Output is correct |
41 | Correct | 5 ms | 5120 KB | Output is correct |
42 | Correct | 4 ms | 5120 KB | Output is correct |
43 | Correct | 4 ms | 5120 KB | Output is correct |
44 | Correct | 4 ms | 5120 KB | Output is correct |
45 | Correct | 4 ms | 5120 KB | Output is correct |
46 | Correct | 4 ms | 5120 KB | Output is correct |
47 | Correct | 4 ms | 5120 KB | Output is correct |
48 | Correct | 4 ms | 5248 KB | Output is correct |
49 | Correct | 4 ms | 5248 KB | Output is correct |
50 | Correct | 4 ms | 5120 KB | Output is correct |
51 | Correct | 4 ms | 5120 KB | Output is correct |
52 | Correct | 4 ms | 5120 KB | Output is correct |
53 | Correct | 4 ms | 5120 KB | Output is correct |
54 | Correct | 4 ms | 5120 KB | Output is correct |
55 | Correct | 4 ms | 5120 KB | Output is correct |
56 | Correct | 4 ms | 5120 KB | Output is correct |
57 | Correct | 5 ms | 5248 KB | Output is correct |
58 | Correct | 4 ms | 5120 KB | Output is correct |
59 | Correct | 4 ms | 5120 KB | Output is correct |
60 | Correct | 4 ms | 5248 KB | Output is correct |
61 | Correct | 4 ms | 5120 KB | Output is correct |
62 | Correct | 4 ms | 5248 KB | Output is correct |
63 | Correct | 4 ms | 5120 KB | Output is correct |
64 | Correct | 188 ms | 13432 KB | Output is correct |
65 | Correct | 178 ms | 13560 KB | Output is correct |
66 | Correct | 172 ms | 13304 KB | Output is correct |
67 | Correct | 177 ms | 13456 KB | Output is correct |
68 | Correct | 173 ms | 13432 KB | Output is correct |
69 | Correct | 175 ms | 13436 KB | Output is correct |
70 | Correct | 171 ms | 13380 KB | Output is correct |
71 | Correct | 169 ms | 13432 KB | Output is correct |
72 | Correct | 170 ms | 13432 KB | Output is correct |
73 | Correct | 185 ms | 25976 KB | Output is correct |
74 | Correct | 190 ms | 25976 KB | Output is correct |
75 | Correct | 176 ms | 13176 KB | Output is correct |
76 | Correct | 168 ms | 13176 KB | Output is correct |
77 | Correct | 189 ms | 13176 KB | Output is correct |
78 | Correct | 193 ms | 13160 KB | Output is correct |
79 | Correct | 179 ms | 13180 KB | Output is correct |
80 | Correct | 207 ms | 13176 KB | Output is correct |
81 | Correct | 154 ms | 13680 KB | Output is correct |
82 | Correct | 173 ms | 13428 KB | Output is correct |
83 | Correct | 188 ms | 18424 KB | Output is correct |
84 | Correct | 194 ms | 20600 KB | Output is correct |
85 | Correct | 193 ms | 20472 KB | Output is correct |
86 | Correct | 194 ms | 14712 KB | Output is correct |
87 | Correct | 181 ms | 14072 KB | Output is correct |
88 | Correct | 174 ms | 14712 KB | Output is correct |
89 | Correct | 184 ms | 14584 KB | Output is correct |
90 | Correct | 178 ms | 14456 KB | Output is correct |
91 | Correct | 165 ms | 14612 KB | Output is correct |
92 | Correct | 165 ms | 14956 KB | Output is correct |
93 | Correct | 176 ms | 17396 KB | Output is correct |
94 | Correct | 158 ms | 19128 KB | Output is correct |
95 | Correct | 156 ms | 17780 KB | Output is correct |
96 | Correct | 169 ms | 15920 KB | Output is correct |
97 | Correct | 171 ms | 14456 KB | Output is correct |
98 | Correct | 174 ms | 13944 KB | Output is correct |
99 | Correct | 172 ms | 13816 KB | Output is correct |
100 | Correct | 168 ms | 16868 KB | Output is correct |
101 | Correct | 168 ms | 14840 KB | Output is correct |
102 | Correct | 166 ms | 14152 KB | Output is correct |
103 | Correct | 175 ms | 13944 KB | Output is correct |
104 | Correct | 107 ms | 14060 KB | Output is correct |
105 | Correct | 195 ms | 22776 KB | Output is correct |
106 | Correct | 111 ms | 14056 KB | Output is correct |
107 | Correct | 120 ms | 14000 KB | Output is correct |
108 | Correct | 216 ms | 26744 KB | Output is correct |
109 | Correct | 103 ms | 14096 KB | Output is correct |
110 | Correct | 191 ms | 27148 KB | Output is correct |
111 | Correct | 164 ms | 13180 KB | Output is correct |