oj.uz

Submission #495749

# Submission time Handle Problem Language Result Execution time Memory
495749 2021-12-20T04:10:54 Z daongocha Power Plant (JOI20_power) C++14
0 / 100
 3 ms 4940 KB 
#include <bits/stdc++.h>

#define ll long long

#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);

using namespace std;

const int MAXN = 2e5 + 5;
int dp[MAXN];
vector<int> path[MAXN];
int a[MAXN];

int ans = 0;

void reroot(int u, int v) {
	dp[u] -= max(dp[v], a[v]);
	dp[v] += max(dp[u], a[u]);
	ans = max(ans, dp[u]);
	ans = max(ans, dp[v]);
}

void dfs(int u, int pre = 0) {
	dp[u] = -a[u];
	for (int v: path[u])
		if (v != pre) {
			dfs(v, u);
			dp[u] += max(dp[v], a[v]);
		}
}

void calc(int u, int pre = 0) {
	ans = max(ans, dp[u]);
	for (int v: path[u]) 
		if (v != pre) {
			reroot(u, v);
			calc(v, u);
			reroot(v, u);
		}
}

signed main() {
	#ifndef PICHU_LOCAL_DEF
		//fileopen1("LAH");
	#endif

	cin.tie(0)->sync_with_stdio(0);

	int n;
	cin >> n;

	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		path[u].push_back(v);
		path[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) {
		char c; cin >> c;
		a[i] = c - '0';
		ans = max(ans, a[i]);
	} 

	dfs(1); for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
	calc(1);

	cout << ans << '\n';
}

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Incorrect 2 ms 4940 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 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Incorrect 2 ms 4940 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 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4940 KB Output is correct
8 Incorrect 2 ms 4940 KB Output isn't correct
9 Halted 0 ms 0 KB -