Submission #928294

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
928294	2024-02-16T07:33:58 Z	vjudge1	Magic Tree (CEOI19_magictree)	C++17	20 / 100	78 ms	18348 KB

magictree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 1e5 + 100;
const ll INF = (ll)1e18 + 100;
const int MOD = 998244353;

int n, m, k, t;
vector<int> g[maxn];
ll d[maxn * 4];
int tin[maxn];
int tout[maxn];
int used[maxn];
ll dp[maxn];

void upd(int i, ll x, int v = 1, int tl = 1, int tr = n){
	if(tl == tr) d[v] = x;
	else{
		int mid = (tl + tr) >> 1;
		if(i <= mid) upd(i, x, v<<1, tl, mid);
		else upd(i, x, v<<1|1, mid+1, tr);
		d[v] = max(d[v<<1], d[v<<1|1]);
	}
}

ll get(int l, int r, int v = 1, int tl = 1, int tr = n){
	if(tr < l || tl > r) return 0;
	if(l <= tl && tr <= r) return d[v];
	int mid = (tl + tr) >> 1;
	return max(get(l, r, v<<1, tl, mid)
	, get(l, r, v<<1|1, mid+1, tr));
}

void calc(int v = 1){
	tin[v] = ++t;
	for(int to: g[v]){
		calc(to);
	}
	tout[v] = t;
}

pii f(tuple<int, int, int> x){
	auto [d, v, w] = x;
	return {d, -tin[v]};
}

void dfs(int v = 1){
	ll sum = 0;
	for(int to: g[v]){
		dfs(to);
		sum += dp[to];
	}
	dp[v] = max(dp[v], sum);
}

void test(){
	cin >> n >> m >> k;
	for(int i = 2; i <= n; i++){
		int p; cin >> p;
		g[p].push_back(i);
	} calc();
	vector<tuple<int, int, int>> q;
	for(int i = 1; i <= m; i++){
		int v, d, w;
		cin >> v >> d >> w;
		q.push_back({d, v, w});
		used[v] = 1;
	}
	for(int i = 1; i <= n; i++){
		if(!used[i]) q.push_back({k + 1, i, 0});
	}
	sort(q.begin(), q.end(), [](tuple<int, int, int> a, tuple<int, int, int> b){
		return f(a) < f(b);
	});
	for(auto [d, v, w]: q){
		dp[v] = w;
		for(int to: g[v]){
			dp[v] += get(tin[to], tout[to]);
		}
		upd(tin[v], dp[v]);
	}
	dfs();
	cout << dp[1];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
	int t; t = 1;
	while(t--) test();
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5464 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	1 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	1 ms	5468 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	2 ms	5468 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	10444 KB	Output is correct
2	Correct	58 ms	14016 KB	Output is correct
3	Correct	65 ms	9644 KB	Output is correct
4	Correct	59 ms	9800 KB	Output is correct
5	Correct	71 ms	10440 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5724 KB	Output is correct
2	Correct	2 ms	5720 KB	Output is correct
3	Correct	2 ms	5724 KB	Output is correct
4	Correct	53 ms	18208 KB	Output is correct
5	Correct	62 ms	18348 KB	Output is correct
6	Correct	77 ms	18116 KB	Output is correct

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	78 ms	10696 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5464 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	1 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	1 ms	5468 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	2 ms	5468 KB	Output is correct
10	Incorrect	67 ms	10440 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	11 ms	8536 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5464 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	1 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	1 ms	5468 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	2 ms	5468 KB	Output is correct
10	Correct	2 ms	5724 KB	Output is correct
11	Correct	2 ms	5720 KB	Output is correct
12	Correct	2 ms	5724 KB	Output is correct
13	Correct	53 ms	18208 KB	Output is correct
14	Correct	62 ms	18348 KB	Output is correct
15	Correct	77 ms	18116 KB	Output is correct
16	Incorrect	67 ms	10440 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #8
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	5464 KB	Output is correct
2	Correct	1 ms	5464 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	1 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	1 ms	5468 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	2 ms	5468 KB	Output is correct
10	Correct	66 ms	10444 KB	Output is correct
11	Correct	58 ms	14016 KB	Output is correct
12	Correct	65 ms	9644 KB	Output is correct
13	Correct	59 ms	9800 KB	Output is correct
14	Correct	71 ms	10440 KB	Output is correct
15	Correct	2 ms	5724 KB	Output is correct
16	Correct	2 ms	5720 KB	Output is correct
17	Correct	2 ms	5724 KB	Output is correct
18	Correct	53 ms	18208 KB	Output is correct
19	Correct	62 ms	18348 KB	Output is correct
20	Correct	77 ms	18116 KB	Output is correct
21	Incorrect	78 ms	10696 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Submission #928294

Compilation message