Submission #453248

#	Time	Username	Problem	Language	Result	Execution time	Memory
453248		fuad27	Power Plant (JOI20_power)	C++14	47 / 100	1574 ms	15500 KiB

power

    #include <bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 4;
    string s;
    vector<int> V[N], dp(N, 0);
    bool vis[N];
     
    void clear(int n) {
    	for(int i=1; i<=n; i++) {
    		dp[i] = 0;
    		vis[i] = 0;
    	}
    }
     
    void dfs(int v, int root) {
    	vis[v] = 1;
    	dp[v] = s[v-1] - '0';
    	int rb = 0, rc = 0;
    	for(int i=0; i<(int) V[v].size(); i++) {
    		int u = V[v][i];
    		if(!vis[u]) {
    			dfs(u, root);
    			rb += dp[u];
    			rc = max(rc, dp[u]);
    		}
    	}
    	if(v == root)
    		dp[v] = rc + 1;
    	else {
    		rb -= s[v-1] - '0';
    		dp[v] = max(dp[v], rb);
    	}
    }
     
    int main() {
    	int n;
    	cin>>n;
    	for(int i=0; i<(n-1); i++) {
    		int a, b;
    		cin>>a>>b;
    		V[a].push_back(b);
    		V[b].push_back(a);
    	}
    	cin>>s;
    	int ans = 0;
    	for(int i=1; i<=n; i++) {
    		if(s[i-1] == '1') {
    			clear(n);
    			dfs(i, i);
    			ans = max(ans, dp[i]);
    		}
    	}
    	cout<<ans;
    }

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