oj.uz

답안 #1031963

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031963 2024-07-23T09:11:15 Z 김은성(#10960) Power Plant (JOI20_power) C++17
0 / 100
 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);
      |     ~~~~~^~~~~~~~~~~~

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 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 -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 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 -