oj.uz

답안 #1031796

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031796 2024-07-23T07:24:25 Z 정민찬(#10962) Power Plant (JOI20_power) C++17
0 / 100
 3 ms 5164 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[200010];

int sz[200010];
int chk[200010];

int getSize(int x, int p) {
	sz[x] = 1;
	for (auto &y : adj[x]) {
		if (y == p || chk[y]) continue;
		sz[x] += getSize(y, x);
	}
	return sz[x];
}

int getCent(int x, int p, int cap) {
	for (auto &y : adj[x]) {
		if (y == p || chk[y]) continue;
		if (sz[y] * 2 > cap) return getCent(y, x, cap);
	}
	return x;
}

int C[200010];
int dp[200010];

void dfs(int x, int p) {
	int sum = 0;
	for (auto &y : adj[x]) {
		if (y == p || chk[y]) continue;
		dfs(y, x);
		sum += dp[y];
	}
	dp[x] = max(C[x], sum - C[x]);
}

int ans = 0;

void dnc(int x) {
	x = getCent(x, -1, getSize(x, -1));
	dfs(x, -1);
	ans = max(ans, dp[x]);
	chk[x] = 1;
	for (auto &y : adj[x]) {
		if (!chk[y]) dnc(y);
	}
}

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin >> n;
	for (int i=0; i<n-1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	string s;
	cin >> s;
	for (int i=1; i<=n; i++) {
		C[i] = s[i-1] - '0';
	}
	dnc(1);
	cout << ans << '\n';
}

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5164 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Incorrect 2 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5164 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Incorrect 2 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 5164 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 3 ms 4956 KB Output is correct
8 Incorrect 2 ms 4956 KB Output isn't correct
9 Halted 0 ms 0 KB -