Submission #1099824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099824		model_code	Tree (IOI24_tree)	C++17	100 / 100	144 ms	23120 KiB

tree

// correct/yiping-full.cpp

#include<bits/stdc++.h>
#include"tree.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

vector<int> fa;
int find(int u){ return fa[u] == u? u: fa[u] = find(fa[u]);}

int n;
ll sumleaf;
vector< array<ll,2> > ans;

ll query(int l,int r)
{
	int k = r / l;
	ll res;
	if(k > n) res = 0;
	else res = l * ans[k][0] + r * ans[k][1];
	return res + l * sumleaf;
}

void init(vector<int> anc, vector<int> wei)
{
	n = (int)anc.size();
	
	vector< vector<int> > g(n);
	for(int i=1; i<n; ++i)
		g[anc[i]].emplace_back(i);
	
	sumleaf = 0;
	for(int i=0; i<n; ++i) if((int)g[i].size() == 0)
	{
		sumleaf += wei[i];
		wei[i] = 0;
	}
	
	ans.resize(n+2);
	fill(ans.begin(), ans.end(), array<ll,2>{0,0});
	
	auto upd = [&] (int k, int w)
	{
		ans[k-1][0] += (ll)k * w;
		ans[k-1][1] += - w;
	};
	
	vector<pii> eff(n);
	for(int i=0; i<n; ++i)
		eff[i] = {wei[i], i};
	sort(eff.begin(), eff.end());
	reverse(eff.begin(), eff.end());
	
	fa.resize(n);
	iota(fa.begin(), fa.end(), 0);
	
	vector<int> num(n, 1), rig(n, eff[0].first);
	
	auto connect = [&] (int u,int v,int cur)
	{
		u = find(u); v = find(v);
		if(u == v) return;
		upd(num[u], rig[u] - cur);
		upd(num[v], rig[v] - cur);
		num[v] += num[u];
		rig[v] = cur;
		fa[u] = v;
	};
	
	vector<int> val(n, 0);
	
	for(auto t: eff)
	{
		if(t.first == 0) break;
		
		int u = t.second;
		val[u] = 1;
		
		if(anc[u] >= 0 && val[anc[u]])
			connect(u, anc[u], t.first);
		for(int v: g[u])
			connect(v, u, t.first);
		
		int v = find(u);
		if(rig[v] != t.first)
			upd(num[v], rig[v] - t.first);
		--num[v];
		rig[v] = t.first;
	}
	
	for(int i=0; i<n; ++i) if(fa[i] == i)
		upd(num[i], rig[i]);
	
	for(int i=n; i>=1; --i)
	{
		ans[i][0] += ans[i+1][0];
		ans[i][1] += ans[i+1][1];
	}
}

vector<ll> tree(vector<int> anc, vector<int> wei, vector<int> L, vector<int> R)
{
	init(anc, wei);
	
	vector<ll> res(L.size());
	for(int i=0; i<(int)L.size(); ++i)
		res[i] = query(L[i], R[i]);
	return res;
}

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