oj.uz

답안 #933046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -