Submission #1101134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101134		rainboy	Tree (IOI24_tree)	C++17	100 / 100	182 ms	57492 KiB

tree

#include "tree.h"
#include <cstdlib>
#include <cstring>

using namespace std;

typedef vector<int> vi;

const int N = 200000, M = N * 4;

long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int pp[N], ww[N];
int *ej[N], eo[N], ii[N], n;

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int *vv;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
		while (j < k)
			if (vv[ii[j]] == vv[i_])
				j++;
			else if (vv[ii[j]] < vv[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int tt[M]; long long aa[M], bb[M];
int tt_[M]; long long aa_[M], bb_[M];
int hh[M], m;

char active[N]; int ds[N], ss[N], l, r;

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j, int w) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	tt[m] = ss[i], aa[m] = (long long) -(ss[i] + 1) * w, bb[m] = w, m++;
	tt[m] = ss[j], aa[m] = (long long) -(ss[j] + 1) * w, bb[m] = w, m++;
	tt[m] = ss[i] + ss[j], aa[m] = (long long) (ss[i] + ss[j] + 1) * w, bb[m] = -w, m++;
	if (ds[i] > ds[j])
		ds[i] = j, ss[j] += ss[i];
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i, ss[i] += ss[j];
	}
}

long long c;

void init(vi pp_, vi ww_) {
	n = pp_.size();
	for (int i = 0; i < n; i++)
		pp[i] = pp_[i], ww[i] = ww_[i];
	for (int i = 0; i < n; i++)
		ii[i] = i;
	vv = ww, sort(ii, 0, n);
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (int j = 1; j < n; j++)
		append(pp[j], j);
	c = 0;
	for (int i = 0; i < n; i++)
		if (eo[i] == 0)
			c += ww[i];
	memset(active, 0, n * sizeof *active), memset(ds, -1, n * sizeof *ds);
	for (int i = 0; i < n; i++)
		ss[i] = max(eo[i] - 1, 0);
	for (int h = n - 1; h >= 0; h--) {
		int i = ii[h], w = ww[i];
		active[i] = 1;
		tt[m] = ss[i], aa[m] = (long long) (ss[i] + 1) * w, bb[m] = -w, m++;
		if (i > 0 && active[pp[i]] == 1)
			join(i, pp[i], w);
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (active[j] == 1)
				join(i, j, w);
		}
	}
	for (int h = 0; h < m; h++)
		hh[h] = h;
	vv = tt, sort(hh, 0, m);
	for (int h = m - 1; h >= 0; h--) {
		int h_ = hh[h];
		tt_[h] = tt[h_], aa_[h] = aa_[h + 1] + aa[h_], bb_[h] = bb_[h + 1] + bb[h_];
	}
}

long long query(int l, int r) {
	int lower = -1, upper = m;
	while (upper - lower > 1) {
		int h = (lower + upper) / 2;
		if (tt_[h] >= r / l)
			upper = h;
		else
			lower = h;
	}
	return aa_[upper] * l + bb_[upper] * r + c * l;
}

Compilation message (stderr)

tree.cpp: In function 'void append(int, int)':
tree.cpp:24:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• 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