Submission #1237134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237134		LucaIlie	Tree (IOI24_tree)	C++20	100 / 100	88 ms	22452 KiB

tree

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

using namespace std;

const int MAX_N = 2e5;
int n;
int sef[MAX_N], leaves[MAX_N], minW[MAX_N];
long long coefL[MAX_N + 1], coefR[MAX_N + 1];
vector<int> adj[MAX_N];

void endComp(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 = p.size();

	for (int v = 1; v < n; v++)
		adj[p[v]].push_back(v);

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

	for (auto pp: ord) {
		int u = pp.second;

		int a = findSef(u);
		endComp(leaves[a], minW[a] - w[u]);
		for (int v: adj[u]) {
			endComp(leaves[v], minW[v] - w[u]);
			leaves[a] += leaves[v];
			sef[v] = a;
		}
		minW[a] = w[u];
		leaves[a]--;
	}
	endComp(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