Submission #711900

#	Time	Username	Problem	Language	Result	Execution time	Memory
711900		rainboy	Cats or Dogs (JOI18_catdog)	C++17	100 / 100	353 ms	24372 KiB

catdog

#include "catdog.h"
#include <stdlib.h>
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 100000, N_ = 1 << 17, INF = 0x3f3f3f3f;	/* N_ = pow2(ceil(log2(N))) */

int min(int a, int b) { return a < b ? a : b; }

int *ej[N], eo[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 dd[N], pp[N], qq[N], tt[N], ta[N], tb[N];

int dfs1(int p, int i, int d) {
	pp[i] = p, dd[i] = d;
	int s = 1, k_ = 0, j_ = -1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p) {
			int k = dfs1(i, j, d + 1);
			s += k;
			if (k_ < k)
				k_ = k, j_ = j;
		}
	}
	qq[i] = j_;
	tt[i] = j_ == -1 ? i : tt[j_];
	return s;
}

void dfs2(int p, int i, int q) {
	static int time;
	ta[i] = time++;
	int j_ = qq[i]; qq[i] = q;
	if (j_ != -1)
		dfs2(i, j_, q);
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p && j != j_)
			dfs2(i, j, j);
	}
	tb[i] = time;
}

int st[N_ * 2][2][2], n_;

void combine(int aa[][2], int bb[][2], int cc[][2]) {
	static int tt[2][2];
	memset(tt, 0x3f, sizeof tt);
	for (int u = 0; u < 2; u++)
		for (int v = 0; v < 2; v++)
			for (int w = 0; w < 2; w++)
				tt[u][w] = min(tt[u][w], aa[u][v] + bb[v][w]);
	memcpy(cc, tt, sizeof tt);
}

void pul(int i) {
	combine(st[i << 1 | 0], st[i << 1 | 1], st[i]);
}

void update(int i, int x0, int x1) {
	i += n_;
	st[i][0][0] = x0, st[i][0][1] = x1 == INF ? INF : x1 + 1;
	st[i][1][0] = x0 == INF ? INF : x0 + 1, st[i][1][1] = x1;
	while (i > 1)
		pul(i >>= 1);
}

void query(int l, int r, int *x0, int *x1) {
	static int dp[2][2], dq[2][2];
	for (int u = 0; u < 2; u++)
		for (int v = 0; v < 2; v++)
			dp[u][v] = dq[u][v] = u == v ? 0 : INF;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			combine(dp, st[l++], dp);
		if ((r & 1) == 0)
			combine(st[r--], dq, dq);
	}
	combine(dp, dq, dp);
	*x0 = min(dp[0][0], dp[0][1]), *x1 = min(dp[1][0], dp[1][1]);
}

void build(int n) {
	n_ = 1;
	while (n_ < n)
		n_ <<= 1;
	for (int i = 0; i < n; i++) {
		st[n_ + i][0][0] = 0, st[n_ + i][0][1] = 1;
		st[n_ + i][1][0] = 1, st[n_ + i][1][1] = 0;
	}
	for (int i = n_ - 1; i > 0; i--)
		pul(i);
}

int cc[N], dp0[N], dp1[N];

void initialize(int n, vi ii, vi jj) {
	n = ii.size() + 1;
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (int h = 0; h < n - 1; h++) {
		int i = ii[h] - 1, j = jj[h] - 1;
		append(i, j), append(j, i);
	}
	dfs1(-1, 0, 0);
	dfs2(-1, 0, 0);
	memset(cc, -1, n * sizeof *cc);
	build(n);
}

int update_(int i, int c) {
	cc[i] = c;
	while (1) {
		int q = qq[i], p = pp[qq[i]], x0, x1;
		if (p != -1) {
			query(ta[q], ta[tt[q]], &x0, &x1);
			dp0[p] -= x0, dp1[p] -= x1;
		}
		if (cc[i] == 0)
			update(ta[i], dp0[i], INF);
		else if (cc[i] == 1)
			update(ta[i], INF, dp1[i]);
		else
			update(ta[i], dp0[i], dp1[i]);
		query(ta[q], ta[tt[q]], &x0, &x1);
		if (p != -1) {
			dp0[p] += x0, dp1[p] += x1;
			i = p;
		} else
			return min(x0, x1);
	}
}

int cat(int i) {
	i--;
	return update_(i, 0);
}

int dog(int i) {
	i--;
	return update_(i, 1);
}

int neighbor(int i) {
	i--;
	return update_(i, -1);
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 30 / 30
• Subtask 3: 62 / 62