Submission #810994

#	Time	Username	Problem	Language	Result	Execution time	Memory
810994		rainboy	Nestabilnost (COI23_nestabilnost)	C11	100 / 100	607 ms	477372 KiB

code1

#include <stdio.h>
#include <stdlib.h>

#define N	300000
#define LN	19	/* LN = ceil(log2(N)) */
#define N_	(1 << LN)
#define N1	(N * ((LN + 1) * 2 + 4))
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int n;
int aa[N], cc[N];
int *ej[N], eo[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 cc_[N_ * 2];

void build(int k, int l, int r) {
	int m;

	if (r - l == 1) {
		cc_[k] = cc[l];
		return;
	}
	m = (l + r) / 2;
	build(k << 1 | 0, l, m), build(k << 1 | 1, m, r);
	cc_[k] = min(cc_[k << 1 | 0], cc_[k << 1 | 1]);
}

int ll[N1], rr[N1]; long long xx1[N1], xx2[N1], yy[N1], lz1[N1], lz2[N1]; int cc1[N1];

int node(int k, long long x) {
	static int _ = 1;

	xx1[_] = x, xx2[_] = -INF, yy[_] = INF, cc1[_] = cc_[k];
	return _++;
}

void put1(int u, long long z) {
	xx1[u] += z;
	lz1[u] += z;
}

void put2(int u, long long z) {
	xx1[u] += z;
	if (xx2[u] != -INF)
		xx2[u] += z;
	if (yy[u] != INF)
		yy[u] += z;
	lz2[u] += z;
}

void pus(int u) {
	int l, r;
	long long z;
	
	l = ll[u], r = rr[u];
	if (z = lz1[u]) {
		if (xx1[l] > xx1[r])
			put1(l, z);
		else if (xx1[l] < xx1[r])
			put1(r, z);
		else
			put1(l, z), put1(r, z);
		lz1[u] = 0;
	}
	if (z = lz2[u]) {
		put2(l, z), put2(r, z);
		lz2[u] = 0;
	}
}

void pul(int u) {
	int l = ll[u], r = rr[u];
	
	if (xx1[l] > xx1[r]) {
		xx1[u] = xx1[l], xx2[u] = max(xx2[l], xx1[r]);
		yy[u] = min(yy[l], min(xx1[r] + cc1[r], yy[r]));
		cc1[u] = cc1[l];
	} else if (xx1[l] < xx1[r]) {
		xx1[u] = xx1[r], xx2[u] = max(xx1[l], xx2[r]);
		yy[u] = min(min(xx1[l] + cc1[l], yy[l]), yy[r]);
		cc1[u] = cc1[r];
	} else {
		xx1[u] = xx1[l], xx2[u] = max(xx2[l], xx2[r]);
		yy[u] = min(yy[l], yy[r]);
		cc1[u] = min(cc1[l], cc1[r]);
	}
	if (xx2[u] == -INF)
		ll[u] = rr[u] = 0;
}

int merge(int u, int v) {
	if (xx2[u] == -INF) {
		put2(v, xx1[u]);
		return v;
	} else if (xx2[v] == -INF) {
		put2(u, xx1[v]);
		return u;
	} else {
		pus(u), pus(v);
		ll[u] = merge(ll[u], ll[v]), rr[u] = merge(rr[u], rr[v]);
		pul(u);
		return u;
	}
}

int cut_(int k, int l, int r, int ql, int qr, long long x) {
	int u, m;

	if (ql <= l && r <= qr)
		return node(k, x);
	if (qr <= l || r <= ql)
		return node(k, INF);
	u = node(k, INF);
	m = (l + r) / 2;
	ll[u] = cut_(k << 1 | 0, l, m, ql, qr, x), rr[u] = cut_(k << 1 | 1, m, r, ql, qr, x);
	pul(u);
	return u;
}

int cut(int u, int k, int l, int r, int ql, int qr) {
	int m;

	if (ql <= l && r <= qr)
		return u;
	if (qr <= l || r <= ql)
		return node(k, INF);
	if (xx2[u] == -INF)
		return cut_(k, l, r, ql, qr, xx1[u]);
	m = (l + r) / 2;
	pus(u);
	ll[u] = cut(ll[u], k << 1 | 0, l, m, ql, qr), rr[u] = cut(rr[u], k << 1 | 1, m, r, ql, qr);
	pul(u);
	return u;
}

void update(int u, int l, int r, long long x) {
	int m;

	if (xx1[u] <= x)
		return;
	if (xx2[u] < x) {
		put1(u, x - xx1[u]);
		return;
	}
	m = (l + r) / 2;
	pus(u);
	update(ll[u], l, m, x), update(rr[u], m, r, x);
	pul(u);
}

int tt[N]; long long dp[N];

void dfs(int p, int i) {
	int o;

	tt[i] = node(1, 0);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs(i, j);
			tt[i] = merge(tt[i], tt[j]);
		}
	}
	tt[i] = cut(tt[i], 1, 0, n, aa[i], n);
	dp[i] = min(xx1[tt[i]] + cc1[tt[i]], yy[tt[i]]);
	if (p != -1 && aa[p] != aa[i] - 1) {
		if (aa[i] == 0)
			tt[i] = cut(tt[i], 1, 0, n, aa[p], aa[p] + 1);
		else
			tt[i] = node(1, INF);
	}
	update(tt[i], 0, n, dp[i]);
}

int main() {
	int h, i, j;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &cc[i]);
	build(1, 0, n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	dfs(-1, 0);
	printf("%lld\n", dp[0]);
	return 0;
}

Compilation message (stderr)

code1.c: In function 'append':
code1.c:20:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   20 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
code1.c: In function 'pus':
code1.c:67:6: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   67 |  if (z = lz1[u]) {
      |      ^
code1.c:76:6: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   76 |  if (z = lz2[u]) {
      |      ^
code1.c: In function 'main':
code1.c:190:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
code1.c:192:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
code1.c:194:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |   scanf("%d", &cc[i]);
      |   ^~~~~~~~~~~~~~~~~~~
code1.c:199:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 20 / 20
• Subtask 3: 7 / 7
• Subtask 4: 22 / 22
• Subtask 5: 39 / 39