oj.uz

Submission #1031950

# Submission time Handle Problem Language Result Execution time Memory
1031950 2024-07-23T08:59:49 Z 김은성(#10960) Power Plant (JOI20_power) C++17
0 / 100
 3 ms 4956 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] > mx){
                mx2 = mx;
                mx = dp[u];
            }
            else if(dp[u]>mx2)
                mx2 = dp[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);
    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:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(i=0; i<graph[c].size(); i++){
      |              ~^~~~~~~~~~~~~~~~
power.cpp: In function 'int main()':
power.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
power.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d %d", &u, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     scanf(" %s", s+1);
      |     ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4952 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 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct
12 Incorrect 2 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4952 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 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct
12 Incorrect 2 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4952 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 4956 KB Output is correct
10 Correct 2 ms 4956 KB Output is correct
11 Correct 3 ms 4952 KB Output is correct
12 Incorrect 2 ms 4956 KB Output isn't correct
13 Halted 0 ms 0 KB -