Submission #1368038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368038		FaresSTH	Tree (IOI24_tree)	C++20	10 / 100	2094 ms	21280 KiB

tree

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
const int mxn=2e5+5;
vector<int>g[mxn],a(mxn);
ll res=0;
ll dfs(int i,int p,int l,int r){
	if(g[i].empty()){
		res+=1ll*a[i]*l;
		return l;
	}
	ll sum=0;
	for(int j:g[i])if(j!=p)sum+=dfs(j,i,l,r);
	if(sum>=r){
		res+=1ll*a[i]*(sum-r);
		return r;
	}
	return sum;
}
void init(std::vector<int> p, std::vector<int> w){
	for(int i=0;i<(int)p.size();i++)g[p[i]].push_back(i),a[i]=w[i];
}
long long query(int l, int r){
	res=0;
	dfs(0,-1,l,r);
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 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