oj.uz

답안 #293909

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
293909 2020-09-08T13:41:37 Z Mlxa Power Plant (JOI20_power) C++14
0 / 100
 18 ms 23824 KB 
#ifdef LC
#include "pch.h"
#else
#include <bits/stdc++.h>
#endif

using namespace std;
using ll = long long;
#define int ll
#define all(x) x.begin(), x.end()
#define x first
#define y second
#define mp make_pair
#define mt make_tuple

const int N = 1e6 + 10;
int n;
int gen[N];
int dp[N];
vector<int> g[N];
int answer = 1;

void dfs(int v, int p) {
	dp[v] = -gen[v];
	for (int u : g[v]) {
		if (u == p) {
			continue;
		}
		dfs(u, v);
		dp[v] += dp[u];
	}
	dp[v] = max(dp[v], 0LL);
	if (v != p) {
		answer = max(answer, dp[v] + gen[p]);
	}
	dp[v] = max(dp[v], gen[v]);
	answer = max(answer, dp[v]);
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int v, u, i = 0; i < n - 1; ++i) {
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	/*
	for (int i = 0; i < n; ++i) {
		cout << i << ":\t";
		for (int j : g[i]) {
			cout << j << " ";
		}
		cout << endl;
	}
	*/
	string str;
	cin >> str;
	for (int i = 0; i < n; ++i) {
		gen[i] = str[i] == '1';
	}
	dfs(0, 0);
	cout << answer << "\n";
	return 0;
}

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 41.0

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

Subtask #3
0.0 / 53.0

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