Submission #1123268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123268		Mousa_Aboubaker	Tree (IOI24_tree)	C++20	0 / 100	2094 ms	20896 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> p, w;

void init(vector<int> P, vector<int> W) 
{
	p = P, w = W;
	n = (int)p.size();
	adj.resize(n);
	for(int i = 1; i < n; i++)
		adj[p[i]].push_back(i);
}

long long query(int L, int R)
{
	int l = L, r = R;
	vector<long long> all(n, 0);
	auto dfs = [&](auto self, int u) -> void
	{
		if((int)adj[u].size() == 0)
		{
			all[u] = l;
			return;
		}
		long long curr = 0;
		for(auto i: adj[u])
		{
			self(self, i);
			curr += all[i];
		}
		all[u] = min(0ll, r - curr);
	};
	dfs(dfs, 0);
	long long res = 0;
	for(int i = 0; i < n; i++)
		res += w[i] * 1ll * abs(all[i]);
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19