oj.uz

Submission #365994

# Submission time Handle Problem Language Result Execution time Memory
365994 2021-02-12T16:54:34 Z giorgikob Power Plant (JOI20_power) C++14
0 / 100
 4 ms 4972 KB 
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 2e5+5;

int n;
int x,y;
vector<int>gr[N];
int root,root1;
int dp[N];
int answer;
string s;

void dfs(int x,int p){

    for(auto to : gr[x]){
        if(to == p) continue;
        dfs(to,x);
    }

    if(s[x] == '1' && root1 == 0){
        root1 = x;
    }
}

void dfs1(int x,int p){
    for(auto to : gr[x]){
        if(to == p) continue;
        dfs1(to,x);
        dp[x] |= dp[to];
    }

    if(s[x] == '1' && dp[x] == 0){
        dp[x] = 1;
        answer ++;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; i++){
        cin >> x >> y;
        gr[x].pb(y);
        gr[y].pb(x);
    }

    cin >> s;
    s = '0' + s;

    for(int i = 1; i <= n; i++){
        if(gr[i].size() == 1){
            root = i;
            break;
        }
    }

    dfs(root,0);

    dfs1(root1,0);

    cout << answer+1 << endl;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Incorrect 4 ms 4972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Incorrect 4 ms 4972 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4972 KB Output is correct
2 Incorrect 4 ms 4972 KB Output isn't correct
3 Halted 0 ms 0 KB -