Submission #1235557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235557		LucaIlie	Tree (IOI24_tree)	C++20	100 / 100	85 ms	22816 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> sef;
vector<long long> coefL, coefR;

void endComponent(int l, int w) {
	coefL[l] += (long long)l * w;
	coefR[l] -= w;
}

int findSef(int v) {
	if (sef[v] != v)
		sef[v] = findSef(sef[v]);
	return sef[v];
}

void init(vector<int> p, vector<int> w) {
	n = w.size();
	coefL.resize(n + 1);
	coefR.resize(n + 1);
	vector<vector<int>> adj(n);
	for (int v = 1; v < n; v++) 
		adj[p[v]].push_back(v);

	vector<pair<int, int>> order;
	vector<int> leaves(n), minW(n);
	sef.resize(n);
	for (int v = 0; v < n; v++) {
		if (adj[v].empty())
			coefL[n] += w[v];
		else
			order.push_back({w[v], v});
		sef[v] = v;
		leaves[v] = 1;
		minW[v] = w[v];
	}
	sort(order.begin(), order.end());
	reverse(order.begin(), order.end());
	for (auto pp: order) {
		int u = pp.second;

		int a = findSef(u);
		endComponent(leaves[a], minW[a] - w[u]);
		for (int v: adj[u]) {
			endComponent(leaves[v], minW[v] - w[u]);
			leaves[a] += leaves[v];
			sef[v] = a;	
		}
		minW[a] = w[u];
		leaves[a]--;
	}
	endComponent(leaves[0], minW[0]);

	for (int i = n - 1; i >= 0; i--) {
		coefL[i] += coefL[i + 1];
		coefR[i] += coefR[i + 1];
	}
}

long long query(int l, int r) {
	int k = min(n, r / l + 1);
	return l * coefL[k] + r * coefR[k];
}

• 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