Submission #796128

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
796128	2023-07-28T06:45:57 Z	박영우(#10072)	Security Guard (JOI23_guard)	C++17	37 / 100	916 ms	1048576 KB

guard

#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];
ll C[MAX];
ll dp[MAX];
ll rem[MAX];
ll ans = 0;
void dfs(int x, int p = 0) {
	for (auto v : adj[x]) {
		if (v == p) continue;
		ans += C[x];
		if (C[x] + rem[x] < C[v]) {
			rem[v] = 0;
			dp[v] = dp[x] + C[v] - C[x] - rem[x];
		}
		else {
			rem[v] = rem[x] - C[v] + C[x];
			dp[v] = dp[x];
		}
		dfs(v, 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, 0);
	ll mx = 0;
	for (i = 1; i <= N; i++) mx = max(mx, dp[i]);
	cout << ans + mx << ln;
}

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	60 ms	37092 KB	Output is correct
3	Correct	59 ms	37016 KB	Output is correct
4	Correct	62 ms	37128 KB	Output is correct
5	Correct	62 ms	37032 KB	Output is correct
6	Correct	59 ms	37008 KB	Output is correct
7	Correct	59 ms	37056 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct

Subtask #2
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	60 ms	37092 KB	Output is correct
3	Correct	59 ms	37016 KB	Output is correct
4	Correct	62 ms	37128 KB	Output is correct
5	Correct	62 ms	37032 KB	Output is correct
6	Correct	59 ms	37008 KB	Output is correct
7	Correct	59 ms	37056 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	65 ms	37096 KB	Output is correct
11	Correct	66 ms	37068 KB	Output is correct
12	Correct	74 ms	37220 KB	Output is correct
13	Correct	65 ms	37124 KB	Output is correct
14	Correct	83 ms	37120 KB	Output is correct
15	Correct	79 ms	37084 KB	Output is correct
16	Correct	63 ms	37036 KB	Output is correct
17	Correct	67 ms	37104 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	60 ms	37092 KB	Output is correct
3	Correct	59 ms	37016 KB	Output is correct
4	Correct	62 ms	37128 KB	Output is correct
5	Correct	62 ms	37032 KB	Output is correct
6	Correct	59 ms	37008 KB	Output is correct
7	Correct	59 ms	37056 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	65 ms	37096 KB	Output is correct
11	Correct	66 ms	37068 KB	Output is correct
12	Correct	74 ms	37220 KB	Output is correct
13	Correct	65 ms	37124 KB	Output is correct
14	Correct	83 ms	37120 KB	Output is correct
15	Correct	79 ms	37084 KB	Output is correct
16	Correct	63 ms	37036 KB	Output is correct
17	Correct	67 ms	37104 KB	Output is correct
18	Correct	3 ms	7380 KB	Output is correct
19	Correct	109 ms	30056 KB	Output is correct
20	Correct	120 ms	25532 KB	Output is correct
21	Correct	80 ms	18424 KB	Output is correct
22	Correct	104 ms	18560 KB	Output is correct
23	Correct	86 ms	19172 KB	Output is correct
24	Correct	74 ms	19312 KB	Output is correct
25	Correct	78 ms	19060 KB	Output is correct
26	Correct	79 ms	19036 KB	Output is correct
27	Correct	65 ms	19128 KB	Output is correct
28	Correct	115 ms	31772 KB	Output is correct
29	Correct	104 ms	27368 KB	Output is correct
30	Correct	84 ms	21732 KB	Output is correct
31	Correct	67 ms	19012 KB	Output is correct
32	Correct	109 ms	18704 KB	Output is correct
33	Correct	107 ms	18324 KB	Output is correct
34	Correct	114 ms	18392 KB	Output is correct
35	Correct	109 ms	19260 KB	Output is correct
36	Correct	87 ms	19408 KB	Output is correct
37	Correct	99 ms	19348 KB	Output is correct
38	Correct	120 ms	25120 KB	Output is correct
39	Correct	152 ms	28132 KB	Output is correct
40	Correct	103 ms	22332 KB	Output is correct
41	Correct	111 ms	36100 KB	Output is correct
42	Correct	160 ms	36536 KB	Output is correct
43	Correct	97 ms	18540 KB	Output is correct
44	Correct	94 ms	18452 KB	Output is correct
45	Correct	99 ms	18588 KB	Output is correct
46	Correct	85 ms	18452 KB	Output is correct
47	Correct	137 ms	18544 KB	Output is correct
48	Correct	126 ms	18564 KB	Output is correct
49	Correct	112 ms	18560 KB	Output is correct
50	Correct	84 ms	18472 KB	Output is correct
51	Correct	88 ms	18556 KB	Output is correct
52	Correct	77 ms	18512 KB	Output is correct

Subtask #4
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	7380 KB	Output is correct
2	Correct	60 ms	37092 KB	Output is correct
3	Correct	59 ms	37016 KB	Output is correct
4	Correct	62 ms	37128 KB	Output is correct
5	Correct	62 ms	37032 KB	Output is correct
6	Correct	59 ms	37008 KB	Output is correct
7	Correct	59 ms	37056 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	65 ms	37096 KB	Output is correct
11	Correct	66 ms	37068 KB	Output is correct
12	Correct	74 ms	37220 KB	Output is correct
13	Correct	65 ms	37124 KB	Output is correct
14	Correct	83 ms	37120 KB	Output is correct
15	Correct	79 ms	37084 KB	Output is correct
16	Correct	63 ms	37036 KB	Output is correct
17	Correct	67 ms	37104 KB	Output is correct
18	Correct	3 ms	7380 KB	Output is correct
19	Correct	109 ms	30056 KB	Output is correct
20	Correct	120 ms	25532 KB	Output is correct
21	Correct	80 ms	18424 KB	Output is correct
22	Correct	104 ms	18560 KB	Output is correct
23	Correct	86 ms	19172 KB	Output is correct
24	Correct	74 ms	19312 KB	Output is correct
25	Correct	78 ms	19060 KB	Output is correct
26	Correct	79 ms	19036 KB	Output is correct
27	Correct	65 ms	19128 KB	Output is correct
28	Correct	115 ms	31772 KB	Output is correct
29	Correct	104 ms	27368 KB	Output is correct
30	Correct	84 ms	21732 KB	Output is correct
31	Correct	67 ms	19012 KB	Output is correct
32	Correct	109 ms	18704 KB	Output is correct
33	Correct	107 ms	18324 KB	Output is correct
34	Correct	114 ms	18392 KB	Output is correct
35	Correct	109 ms	19260 KB	Output is correct
36	Correct	87 ms	19408 KB	Output is correct
37	Correct	99 ms	19348 KB	Output is correct
38	Correct	120 ms	25120 KB	Output is correct
39	Correct	152 ms	28132 KB	Output is correct
40	Correct	103 ms	22332 KB	Output is correct
41	Correct	111 ms	36100 KB	Output is correct
42	Correct	160 ms	36536 KB	Output is correct
43	Correct	97 ms	18540 KB	Output is correct
44	Correct	94 ms	18452 KB	Output is correct
45	Correct	99 ms	18588 KB	Output is correct
46	Correct	85 ms	18452 KB	Output is correct
47	Correct	137 ms	18544 KB	Output is correct
48	Correct	126 ms	18564 KB	Output is correct
49	Correct	112 ms	18560 KB	Output is correct
50	Correct	84 ms	18472 KB	Output is correct
51	Correct	88 ms	18556 KB	Output is correct
52	Correct	77 ms	18512 KB	Output is correct
53	Correct	3 ms	7380 KB	Output is correct
54	Runtime error	916 ms	1048576 KB	Execution killed with signal 9
55	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	5 ms	7300 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	5 ms	7300 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	60 ms	37092 KB	Output is correct
3	Correct	59 ms	37016 KB	Output is correct
4	Correct	62 ms	37128 KB	Output is correct
5	Correct	62 ms	37032 KB	Output is correct
6	Correct	59 ms	37008 KB	Output is correct
7	Correct	59 ms	37056 KB	Output is correct
8	Correct	3 ms	7380 KB	Output is correct
9	Correct	4 ms	7380 KB	Output is correct
10	Correct	65 ms	37096 KB	Output is correct
11	Correct	66 ms	37068 KB	Output is correct
12	Correct	74 ms	37220 KB	Output is correct
13	Correct	65 ms	37124 KB	Output is correct
14	Correct	83 ms	37120 KB	Output is correct
15	Correct	79 ms	37084 KB	Output is correct
16	Correct	63 ms	37036 KB	Output is correct
17	Correct	67 ms	37104 KB	Output is correct
18	Correct	3 ms	7380 KB	Output is correct
19	Correct	109 ms	30056 KB	Output is correct
20	Correct	120 ms	25532 KB	Output is correct
21	Correct	80 ms	18424 KB	Output is correct
22	Correct	104 ms	18560 KB	Output is correct
23	Correct	86 ms	19172 KB	Output is correct
24	Correct	74 ms	19312 KB	Output is correct
25	Correct	78 ms	19060 KB	Output is correct
26	Correct	79 ms	19036 KB	Output is correct
27	Correct	65 ms	19128 KB	Output is correct
28	Correct	115 ms	31772 KB	Output is correct
29	Correct	104 ms	27368 KB	Output is correct
30	Correct	84 ms	21732 KB	Output is correct
31	Correct	67 ms	19012 KB	Output is correct
32	Correct	109 ms	18704 KB	Output is correct
33	Correct	107 ms	18324 KB	Output is correct
34	Correct	114 ms	18392 KB	Output is correct
35	Correct	109 ms	19260 KB	Output is correct
36	Correct	87 ms	19408 KB	Output is correct
37	Correct	99 ms	19348 KB	Output is correct
38	Correct	120 ms	25120 KB	Output is correct
39	Correct	152 ms	28132 KB	Output is correct
40	Correct	103 ms	22332 KB	Output is correct
41	Correct	111 ms	36100 KB	Output is correct
42	Correct	160 ms	36536 KB	Output is correct
43	Correct	97 ms	18540 KB	Output is correct
44	Correct	94 ms	18452 KB	Output is correct
45	Correct	99 ms	18588 KB	Output is correct
46	Correct	85 ms	18452 KB	Output is correct
47	Correct	137 ms	18544 KB	Output is correct
48	Correct	126 ms	18564 KB	Output is correct
49	Correct	112 ms	18560 KB	Output is correct
50	Correct	84 ms	18472 KB	Output is correct
51	Correct	88 ms	18556 KB	Output is correct
52	Correct	77 ms	18512 KB	Output is correct
53	Correct	3 ms	7380 KB	Output is correct
54	Runtime error	916 ms	1048576 KB	Execution killed with signal 9
55	Halted	0 ms	0 KB	-

Submission #796128

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 13.0 / 13.0

Subtask #3 12.0 / 12.0

Subtask #4 0 / 13.0

Subtask #5 0 / 8.0

Subtask #6 0 / 18.0

Subtask #7 0 / 24.0

Subtask #1
12.0 / 12.0

Subtask #2
13.0 / 13.0

Subtask #3
12.0 / 12.0

Subtask #4
0 / 13.0

Subtask #5
0 / 8.0

Subtask #6
0 / 18.0

Subtask #7
0 / 24.0