Submission #365994

#	Time	Username	Problem	Language	Result	Execution time	Memory
365994		giorgikob	Power Plant (JOI20_power)	C++14	0 / 100	4 ms	4972 KiB

power

#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 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 53