oj.uz

답안 #825835

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
825835 2023-08-15T08:41:39 Z Hakiers Power Plant (JOI20_power) C++17
0 / 100
 2 ms 4948 KB 
#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int MAXN = 2e5 + 7;
vector<int> G[MAXN];
bool generator[MAXN];
int dp[MAXN][2]; 
// dp[v][1] idziemy w gore, dp[v][0] najlepszy wynik dla poddrzewa
int n;

void dfs(int v, int p){

    int sumson = 0;


    for(auto u : G[v]){
        if(u == p) continue;
        dfs(u, v);
        sumson += dp[u][1];
        dp[v][0] = max(dp[v][0], dp[u][0]); // wyniki dla poddrzew
        if(generator[v]) dp[v][0] = max(dp[v][0], dp[u][1] + 1); // jezeli jakas sciezka konczy sie w nas 
    }

     // jezeli laczymy wszystkie poddrzewa i przechodzi przez nas 
    if(generator[v]) dp[v][0] = max(dp[v][0], sumson - 1);
    else dp[v][0] = max(dp[v][0], sumson);


    if(generator[v]) 
        dp[v][1] = max(sumson - 1, 1);
    else 
        dp[v][1] = sumson;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        G[a].push_back({b});
        G[b].push_back({a});
    }

    string s;
    cin >> s;
    s = "#" + s;
    for(int i = 1; i <= n; i++)
        generator[i] = (s[i] - '0');

    dfs(1, 1);

    cout << dp[1][0] << endl;
    
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -