| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1031963 |
2024-07-23T09:11:15 Z |
김은성(#10960) |
Power Plant (JOI20_power) |
C++17 |
|
2 ms |
5236 KB |
#include <bits/stdc++.h>
using namespace std;
bool ch[200009];
int ch2[200009], cnt = 0;
vector<int> graph[200009];
int a[200009], sz[200009], dp[200009], ans = 0;
char s[200009];
void getsize(int v){
ch2[v] = cnt;
sz[v] = 1;
for(int i=0; i<graph[v].size(); i++){
int u = graph[v][i];
if(!ch[u] && ch2[u] != cnt){
getsize(u);
sz[v] += sz[u];
}
}
}
int centroid(int v, int crit){
ch2[v] = cnt;
//printf("v=%d sz=%d crit=%d\n", v, sz[v], crit);
for(int i=0; i<graph[v].size(); i++){
int u = graph[v][i];
if(!ch[u] && ch2[u] != cnt){
if(sz[u] > crit)
return centroid(u, crit);
}
}
return v;
}
void treedp(int v){
ch2[v] = cnt;
int sum = 0, mx = 0;
for(int i=0; i<graph[v].size(); i++){
int u = graph[v][i];
if(!ch[u] && ch2[u] != cnt){
treedp(u);
sum += dp[u];
mx = max(mx, dp[u]);
}
}
dp[v] = max(max(a[v], mx), sum - a[v]);
// printf("v=%d sum=%d dp[v]=%d\n", v, sum,dp[v]);
}
void solve(int v){
cnt++;
getsize(v);
cnt++;
int c=centroid(v, sz[v]/2), i, u, temp = 1;
ch[c]=1;
for(i=0; i<graph[c].size(); i++){
u = graph[c][i];
if(!ch[u]){
if(a[u] && a[c])
temp = 2;
}
}
cnt++;
treedp(c);
int mx = 0, mx2 = 0;
for(i=0; i<graph[c].size(); i++){
u = graph[c][i];
if(!ch[u]){
if(dp[u] > 0 && a[c])
temp = max(temp, 2);
}
}
//temp = max(mx + mx2 - a[c], temp);
temp = max(dp[c], temp);
//printf("c=%d temp[c]=%d\n", c, temp);
if(a[c]){
int temp2 = 0;
for(i=0; i<graph[c].size(); i++){
u = graph[c][i];
if(!ch[u]){
temp2 = max(temp2, dp[u]);
}
}
temp = max(temp, temp2 + 1);
}
ans = max(ans, temp);
for(i=0; i<graph[c].size(); i++){
u = graph[c][i];
if(!ch[u]){
solve(u);
}
}
}
int main(){
int n, u, b, i;
scanf("%d", &n);
for(i=1; i<n; i++){
scanf("%d %d", &u, &b);
graph[u].push_back(b);
graph[b].push_back(u);
}
scanf(" %s", s+1);
for(i=1; i<=n; i++){
//printf("s=%d\n", s[i]);
a[i] = s[i] - '0';
}
solve(1);
printf("%d\n", ans);
return 0;
}
Compilation message
power.cpp: In function 'void getsize(int)':
power.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
11 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp: In function 'int centroid(int, int)':
power.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp: In function 'void treedp(int)':
power.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i=0; i<graph[v].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp: In function 'void solve(int)':
power.cpp:51:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(i=0; i<graph[c].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(i=0; i<graph[c].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(i=0; i<graph[c].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp:82:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for(i=0; i<graph[c].size(); i++){
| ~^~~~~~~~~~~~~~~~
power.cpp:60:9: warning: unused variable 'mx' [-Wunused-variable]
60 | int mx = 0, mx2 = 0;
| ^~
power.cpp:60:17: warning: unused variable 'mx2' [-Wunused-variable]
60 | int mx = 0, mx2 = 0;
| ^~~
power.cpp: In function 'int main()':
power.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
91 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
power.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | scanf("%d %d", &u, &b);
| ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf(" %s", s+1);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4968 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 9 |
Correct |
2 ms |
5236 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4964 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4968 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 9 |
Correct |
2 ms |
5236 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4964 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4968 KB |
Output is correct |
| 3 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 9 |
Correct |
2 ms |
5236 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4956 KB |
Output is correct |
| 11 |
Correct |
2 ms |
4964 KB |
Output is correct |
| 12 |
Incorrect |
2 ms |
4956 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
