oj.uz

Submission #933046

# Submission time Handle Problem Language Result Execution time Memory
933046 2024-02-24T23:08:29 Z Cyber_Wolf Magic Tree (CEOI19_magictree) C++17
21 / 100
 84 ms 33632 KB 
#include <bits/stdc++.h>

using namespace std;

#define lg long long
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const lg N = 1e5+5;

lg n, m, k;
lg v[N], d[N];
vector<lg> adj[N];
map<lg, lg> mp2;

void solve(lg src)
{
	map<lg, lg> mp;
	mp[0] = 0; 
	for(auto it : adj[src])
	{
		solve(it);
		if(mp.size() < mp2.size())
		{
			swap(mp, mp2);
		}
		for(auto [it, fr] : mp2)
		{
			mp[it] += fr;
		}
	}
	if(d[src])
	{
		mp[d[src]] += v[src];
		while(mp.size() > 1 && ((--mp.end())->second) <= v[src] && ((--mp.end())->first) > d[src] && v[src] >= 0)
		{
			v[src] -= ((--mp.end())->second);
			mp.erase(--mp.end());
		}
		while(mp.size() > 1 && ((--mp.end())->first) > d[src] && v[src] >= 0)
		{
			((--mp.end())->second) -= v[src];
			break;
		}
	} 
	swap(mp, mp2);
	return ;
}

int main()
{
	fastio;
	cin >> n >> m >> k;
	for(int i = 2; i <= n; i++)
	{
		lg p;
		cin >> p;
		adj[p].push_back(i);
	}
	for(int i = 1; i <= m; i++)
	{
		lg node, day, score;
		cin >> node >> day >> score;
		d[node] = day;
		v[node] = score;
	}
	solve(1);
	lg ans = 0;
	for(auto [a, b] : mp2)	ans += b;
	cout << ans << '\n';

    return 0;
}


/*
dp[src][max] = max(dp[par][v[i]]+w[i], dp[src][max-1])
*/

Subtask #1
6.0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8784 KB Output is correct
2 Correct 38 ms 16980 KB Output is correct
3 Correct 84 ms 11944 KB Output is correct
4 Correct 51 ms 10188 KB Output is correct
5 Correct 69 ms 12788 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7884 KB Output is correct
2 Correct 36 ms 7504 KB Output is correct
3 Correct 42 ms 18256 KB Output is correct
4 Correct 30 ms 6112 KB Output is correct
5 Correct 44 ms 33632 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Incorrect 40 ms 7516 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3676 KB Output is correct
2 Correct 18 ms 6944 KB Output is correct
3 Correct 27 ms 6748 KB Output is correct
4 Correct 18 ms 6876 KB Output is correct
5 Correct 10 ms 5504 KB Output is correct
6 Incorrect 20 ms 11592 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2908 KB Output is correct
11 Incorrect 1 ms 2908 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 37 ms 8784 KB Output is correct
11 Correct 38 ms 16980 KB Output is correct
12 Correct 84 ms 11944 KB Output is correct
13 Correct 51 ms 10188 KB Output is correct
14 Correct 69 ms 12788 KB Output is correct
15 Correct 1 ms 2908 KB Output is correct
16 Incorrect 1 ms 2908 KB Output isn't correct
17 Halted 0 ms 0 KB -