Submission #928297

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
928297	2024-02-16T07:35:44 Z	vjudge1	Magic Tree (CEOI19_magictree)	C++17	20 / 100	85 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});
	}
	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	5468 KB	Output is correct
2	Correct	3 ms	5468 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	2 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	2 ms	5464 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	1 ms	5468 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	9676 KB	Output is correct
2	Correct	29 ms	13140 KB	Output is correct
3	Correct	55 ms	9668 KB	Output is correct
4	Correct	49 ms	9552 KB	Output is correct
5	Correct	58 ms	10444 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	5724 KB	Output is correct
3	Correct	1 ms	5724 KB	Output is correct
4	Correct	54 ms	18128 KB	Output is correct
5	Correct	63 ms	18348 KB	Output is correct
6	Correct	85 ms	18092 KB	Output is correct

Subtask #4
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	68 ms	10500 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	5468 KB	Output is correct
2	Correct	3 ms	5468 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	2 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	2 ms	5464 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	1 ms	5468 KB	Output is correct
10	Incorrect	66 ms	10276 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	8028 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	5468 KB	Output is correct
2	Correct	3 ms	5468 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	2 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	2 ms	5464 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	1 ms	5468 KB	Output is correct
10	Correct	2 ms	5724 KB	Output is correct
11	Correct	2 ms	5724 KB	Output is correct
12	Correct	1 ms	5724 KB	Output is correct
13	Correct	54 ms	18128 KB	Output is correct
14	Correct	63 ms	18348 KB	Output is correct
15	Correct	85 ms	18092 KB	Output is correct
16	Incorrect	66 ms	10276 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	5468 KB	Output is correct
2	Correct	3 ms	5468 KB	Output is correct
3	Correct	1 ms	5468 KB	Output is correct
4	Correct	1 ms	5468 KB	Output is correct
5	Correct	2 ms	5468 KB	Output is correct
6	Correct	1 ms	5468 KB	Output is correct
7	Correct	2 ms	5464 KB	Output is correct
8	Correct	1 ms	5468 KB	Output is correct
9	Correct	1 ms	5468 KB	Output is correct
10	Correct	30 ms	9676 KB	Output is correct
11	Correct	29 ms	13140 KB	Output is correct
12	Correct	55 ms	9668 KB	Output is correct
13	Correct	49 ms	9552 KB	Output is correct
14	Correct	58 ms	10444 KB	Output is correct
15	Correct	2 ms	5724 KB	Output is correct
16	Correct	2 ms	5724 KB	Output is correct
17	Correct	1 ms	5724 KB	Output is correct
18	Correct	54 ms	18128 KB	Output is correct
19	Correct	63 ms	18348 KB	Output is correct
20	Correct	85 ms	18092 KB	Output is correct
21	Incorrect	68 ms	10500 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Submission #928297

Compilation message