Submission #359344

#	Time	Username	Problem	Language	Result	Execution time	Memory
359344		eyangch	Power Plant (JOI20_power)	C++17	47 / 100	226 ms	39388 KiB

power

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

int N;
vector<int> graph[200000];
char s[200000];
bool vis[200000];
int ans = 0;

int dfs(int id){
    if(vis[id]) return 0;
    vis[id] = true;
    int p = s[id] - '0';
    int ret = p;
    int c = 0;
    int mxc = 0;
    for(int i : graph[id]){
        int cur = dfs(i);
        if(cur == 0) continue;
        c++;
        mxc = max(mxc, cur);
        ret += cur;
    }
    if(p && c > 0){
        if(c == 1){
            ans = max(ans, ret);
            (--ret)--;
        }else{
            (--ret)--;
            ans = max({ans, ret, mxc+1});
        }
    }
    ans = max(ans, ret);
    return max(p, ret);
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int i = 0; i < N-1; i++){
        int a, b; cin >> a >> b;
        graph[a-1].push_back(b-1);
        graph[b-1].push_back(a-1);
    }
    cin >> s;
    dfs(0);
    cout << ans << endl;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 0 / 53