oj.uz

Submission #434924

# Submission time Handle Problem Language Result Execution time Memory
434924 2021-06-22T09:54:39 Z xuliu Power Plant (JOI20_power) C++14
0 / 100
 5 ms 5812 KB 
#include <bits/stdc++.h>
using namespace std;

// Power - subtask 2

#define ll long long
#define ull unsigned LL
#define ld long double
#define debug if(0)
#define fastio ios_base::sync_with_stdio(0); cin.tie()

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) {
	vis[v] = 1;
	dp[v] = s[v-1] - '0';
	int rb = -(s[v-1] - '0');
	for(int i=0; i<(int) V[v].size(); i++) {
		int u = V[v][i];
		if(!vis[u]) {
			dfs(u);
			rb += dp[u];
		}
	}
	dp[v] = max(dp[v], rb);
}

int main() {
	fastio;
	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++) {
		clear(n);
		dfs(i);
		ans = max(ans, dp[i]);
	}
	cout<<ans;
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 5 ms 5812 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 5 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 5 ms 5708 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Incorrect 5 ms 5708 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 5 ms 5812 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 5 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 5 ms 5708 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Incorrect 5 ms 5708 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5708 KB Output is correct
2 Correct 5 ms 5812 KB Output is correct
3 Correct 4 ms 5708 KB Output is correct
4 Correct 5 ms 5708 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 5 ms 5708 KB Output is correct
7 Correct 5 ms 5708 KB Output is correct
8 Incorrect 5 ms 5708 KB Output isn't correct
9 Halted 0 ms 0 KB -