oj.uz

Submission #933042

# Submission time Handle Problem Language Result Execution time Memory
933042 2024-02-24T23:01:58 Z Cyber_Wolf Magic Tree (CEOI19_magictree) C++17
15 / 100
 81 ms 34668 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.erase(--mp.end());
		}
		auto it = mp.end();
		it--;
		while((it->first) > d[src])
		{
			it->second -= v[src];
			if(it == mp.begin())	break;
			it--;
		}
	} 
	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
0 / 6.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 8788 KB Output is correct
2 Correct 39 ms 17232 KB Output is correct
3 Correct 81 ms 11604 KB Output is correct
4 Correct 49 ms 9932 KB Output is correct
5 Correct 60 ms 12368 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7516 KB Output is correct
2 Correct 35 ms 8280 KB Output is correct
3 Correct 41 ms 19064 KB Output is correct
4 Correct 28 ms 6868 KB Output is correct
5 Correct 45 ms 34668 KB Output is correct

Subtask #5
0 / 16.0

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

Subtask #6
0 / 13.0

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

Subtask #7
0 / 22.0

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

Subtask #8
0 / 17.0

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