oj.uz

Submission #796099

# Submission time Handle Problem Language Result Execution time Memory
796099 2023-07-28T06:24:53 Z 박영우(#10072) Security Guard (JOI23_guard) C++17
0 / 100
 73 ms 30780 KB 
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 301010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<int> adj[MAX];
int C[MAX];
int rem[MAX];
ll ans = 0;
void dfs(int x, int p = 0) {
	if (adj[x].size() == 1 && p) {
		rem[x] = C[x];
		ans += C[x];
		return;
	}
	for (auto v : adj[x]) if (v != p) {
		dfs(v, x);
		if (rem[v] >= C[x]) rem[x] += rem[v] - C[x];
	}
	for (auto v : adj[x]) if (v != p) {
		if (rem[v] < C[x]) {
			rem[x] -= C[x] - rem[v];
			ans += C[x] - rem[v];
		}
	}
	if (rem[x] < 0) {
		ans -= rem[x];
		rem[x] = 0;
	}
	if (!p) return;
	if (rem[x] < C[x]) {
		ans += C[x] - rem[x];
		rem[x] = C[x];
	}
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, Q;
	cin >> N >> M >> Q;
	int i;
	for (i = 1; i <= N; i++) cin >> C[i];
	int a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	dfs(1);
	cout << ans << ln;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 73 ms 30776 KB Output is correct
3 Correct 62 ms 30780 KB Output is correct
4 Incorrect 63 ms 30748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 73 ms 30776 KB Output is correct
3 Correct 62 ms 30780 KB Output is correct
4 Incorrect 63 ms 30748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 73 ms 30776 KB Output is correct
3 Correct 62 ms 30780 KB Output is correct
4 Incorrect 63 ms 30748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 73 ms 30776 KB Output is correct
3 Correct 62 ms 30780 KB Output is correct
4 Incorrect 63 ms 30748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Incorrect 4 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Incorrect 4 ms 7380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 73 ms 30776 KB Output is correct
3 Correct 62 ms 30780 KB Output is correct
4 Incorrect 63 ms 30748 KB Output isn't correct
5 Halted 0 ms 0 KB -