Submission #867914

#	Time	Username	Problem	Language	Result	Execution time	Memory
867914		parsadox2	Magic Tree (CEOI19_magictree)	C++14	3 / 100	91 ms	16572 KiB

magictree

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n , m , k , tree[N << 2] , st_tim[N] , fn_tim[N] , tim;
vector <int> adj[N];
set <int> st;

struct fruit{
	int v , d , w;
};
vector <fruit> all;

bool cmp(fruit a , fruit b)
{
	return a.d > b.d;
}

void Dfs(int v)
{
	st_tim[v] = tim++;
	for(auto u : adj[v])
		Dfs(u);
	fn_tim[v] = tim;
}

int Get(int l , int r , int node = 1 , int nl = 0 , int nr = n)
{
	if(r <= nl || nr <= l)
		return 0;
	if(l <= nl && nr <= r)
		return tree[node];
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	return Get(l , r , lc , nl , mid) + Get(l , r , rc , mid , nr);
}

void Add(int ind , int val , int node = 1 , int nl = 0 , int nr = n)
{
	tree[node] += val;
	if(nr - nl == 1)
		return;
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(ind < mid)
		Add(ind , val , lc , nl , mid);
	else
		Add(ind , val , rc , mid , nr);
}

void Res(int ind , int node = 1 , int nl = 0 , int nr = n)
{
	if(nr - nl == 1)
	{
		tree[node] = 0;
		return;
	}
	int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
	if(ind < mid)
		Res(ind , lc , nl , mid);
	else
		Res(ind , rc , mid , nr);
	tree[node] = tree[lc] + tree[rc];
}

void ins(fruit a)
{
	st.insert(st_tim[a.v]);
	Add(st_tim[a.v] , a.w);
	auto it = st.upper_bound(st_tim[a.v]);
	if(it == st.end())
		return;
	int now = *it;
	vector <int> rem;
	while(now < fn_tim[a.v])
	{
		rem.push_back(now);
		Res(now);
		it++;
		if(it == st.end())
			break;
		now = *it;
	}
	for(auto u : rem)
		st.erase(u);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 2 ; i <= n ; i++)
	{
		int x;  cin >> x;
		adj[x].push_back(i);
	}
	for(int i = 0 ; i < m ; i++)
	{
		int v , d , w;  cin >> v >> d >> w;
		all.push_back({v , d , w});
	}
	sort(all.begin() , all.end() , cmp);
	Dfs(1);
	int ans = 0;
	for(auto u : all)
	{
		int val = Get(st_tim[u.v] , fn_tim[u.v]);
		if(u.w > val)
		{
			ans += u.w - val;
			ins(u);
		}
	}
	cout << ans << endl;
	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 3 / 3
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 16
• Subtask 6: 0 / 13
• Subtask 7: 0 / 22
• Subtask 8: 0 / 17