oj.uz

Submission #310500

# Submission time Handle Problem Language Result Execution time Memory
310500 2020-10-07T07:18:44 Z georgerapeanu Power Plant (JOI20_power) C++11
0 / 100
 4 ms 4992 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int n;
vector<int> graph[200005];
string s;

int dp[200005];
int sum[200005];

void predfs(int nod,int tata){
    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }
        predfs(it,nod);
        sum[nod] += dp[it];
    }

    if(s[nod] == '1'){
        dp[nod] = max(1,sum[nod] - 1);
    }
    else{
        dp[nod] = sum[nod];
    }
}

int ans = 0;

void dfs(int nod,int tata){
    ans = max(ans,dp[nod]);

    for(auto it:graph[nod]){
        if(it == tata){
            continue;
        }

        sum[nod] -= dp[it];
        if(s[nod] == '1'){
            dp[nod] = max(1,sum[nod] - 1);
        }
        else{
            dp[nod] = sum[nod];
        }
        sum[it] += dp[nod];
        if(s[it] == '1'){
            dp[it] = max(1,sum[it] - 1);
        }
        else{
            dp[it] = sum[it];
        }

        dfs(it,nod);

        sum[it] -= dp[nod];
        if(s[it] == '1'){
            dp[it] = max(1,sum[it] - 1);
        }
        else{
            dp[it] = sum[it];
        }

        sum[nod] += dp[it];
        if(s[nod] == '1'){
            dp[nod] = max(1,sum[nod] - 1);
        }
        else{
            dp[nod] = sum[nod];
        }
    }
}

int main(){

    cin >> n;

    for(int i = 1;i < n;i++){
        int x,y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    cin >> s;

    s = " " + s;

    predfs(1,0);
    dfs(1,0);

    cout << ans << "\n";

    return 0;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Incorrect 4 ms 4992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Incorrect 4 ms 4992 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 4992 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Incorrect 4 ms 4992 KB Output isn't correct
9 Halted 0 ms 0 KB -