oj.uz

Submission #711900

# Submission time Handle Problem Language Result Execution time Memory
711900 2023-03-17T15:55:50 Z rainboy Cats or Dogs (JOI18_catdog) C++17
100 / 100
 353 ms 24372 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 296 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 2 ms 432 KB Output is correct
18 Correct 2 ms 432 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 428 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 428 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 300 KB Output is correct

Subtask #3
62.0 / 62.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 2 ms 432 KB Output is correct
18 Correct 2 ms 432 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 428 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 296 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 428 KB Output is correct
30 Correct 1 ms 304 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 1 ms 300 KB Output is correct
33 Correct 198 ms 8792 KB Output is correct
34 Correct 67 ms 9124 KB Output is correct
35 Correct 190 ms 7132 KB Output is correct
36 Correct 319 ms 15004 KB Output is correct
37 Correct 12 ms 4460 KB Output is correct
38 Correct 353 ms 16312 KB Output is correct
39 Correct 331 ms 16284 KB Output is correct
40 Correct 290 ms 16300 KB Output is correct
41 Correct 299 ms 16284 KB Output is correct
42 Correct 279 ms 16292 KB Output is correct
43 Correct 301 ms 16284 KB Output is correct
44 Correct 250 ms 16316 KB Output is correct
45 Correct 287 ms 16300 KB Output is correct
46 Correct 316 ms 16292 KB Output is correct
47 Correct 318 ms 16336 KB Output is correct
48 Correct 89 ms 11864 KB Output is correct
49 Correct 94 ms 14148 KB Output is correct
50 Correct 35 ms 3512 KB Output is correct
51 Correct 41 ms 5960 KB Output is correct
52 Correct 17 ms 3248 KB Output is correct
53 Correct 164 ms 14572 KB Output is correct
54 Correct 129 ms 6972 KB Output is correct
55 Correct 257 ms 12368 KB Output is correct
56 Correct 155 ms 7880 KB Output is correct
57 Correct 217 ms 14228 KB Output is correct
58 Correct 19 ms 6456 KB Output is correct
59 Correct 43 ms 5196 KB Output is correct
60 Correct 98 ms 13096 KB Output is correct
61 Correct 125 ms 13480 KB Output is correct
62 Correct 60 ms 11200 KB Output is correct
63 Correct 40 ms 10700 KB Output is correct
64 Correct 39 ms 12876 KB Output is correct
65 Correct 63 ms 20264 KB Output is correct
66 Correct 69 ms 5356 KB Output is correct
67 Correct 58 ms 15092 KB Output is correct
68 Correct 116 ms 20684 KB Output is correct
69 Correct 28 ms 2220 KB Output is correct
70 Correct 6 ms 636 KB Output is correct
71 Correct 56 ms 9936 KB Output is correct
72 Correct 68 ms 17964 KB Output is correct
73 Correct 181 ms 24372 KB Output is correct
74 Correct 230 ms 20128 KB Output is correct
75 Correct 132 ms 24332 KB Output is correct
76 Correct 123 ms 22824 KB Output is correct
77 Correct 188 ms 20556 KB Output is correct