oj.uz

Submission #848833

# Submission time Handle Problem Language Result Execution time Memory
848833 2023-09-13T15:01:49 Z rainboy Beech Tree (IOI23_beechtree) C++17
22 / 100
 70 ms 15632 KB 
#include "beechtree.h"
#include <cstdlib>

using namespace std;

typedef vector<int> vi;

const int N = 200000, M = 200000;

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

unsigned int X = 12345;

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

int 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;
}

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 (eo[ii[j]] == eo[i_])
				j++;
			else if (eo[ii[j]] < eo[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;
	}
}

char used[M];

int duplicate(int i) {
	int dup = 0;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (used[cc[j]])
			dup = 1;
		used[cc[j]] = 1;
	}
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		used[cc[j]] = 0;
	}
	return dup;
}

int contains(int i1, int i2) {
	for (int o = eo[i1]; o--; ) {
		int j = ej[i1][o];
		used[cc[j]] = 1;
	}
	int cont = 1;
	for (int o = eo[i2]; o--; ) {
		int j = ej[i2][o];
		if (!used[cc[j]])
			cont = 0;
	}
	for (int o = eo[i1]; o--; ) {
		int j = ej[i1][o];
		used[cc[j]] = 0;
	}
	return cont;
}

int hh[N];

vi beechtree(int n, int m, vi pp, vi cc_) {
	for (int i = 1; i < n; i++)
		cc[i] = cc_[i] - 1;
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (int i = 1; i < n; i++)
		append(pp[i], i);
	int line = 1;
	for (int i = 1; i < n; i++)
		if (pp[i] != i - 1) {
			line = 0;
			break;
		}
	vi ans(n, 0);
	if (line) {
		ans[n - 1] = 1;
		for (int i = n - 2; i >= 0 && cc[i + 1] == cc[n - 1]; i--)
			ans[i] = 1;
	} else
		for (int i = n - 1; i >= 0; i--) {
			hh[i] = 0;
			for (int o = 0; o < eo[i]; o++)
				hh[i] = max(hh[i], hh[ej[i][o]] + 1);
			if (hh[i] > 2) {
				ans[i] = 0;
				continue;
			}
			sort(ej[i], 0, eo[i]);
			ans[i] = !duplicate(i);
			for (int o = 0; o < eo[i]; o++)
				if (duplicate(ej[i][o])) {
					ans[i] = 0;
					break;
				}
			for (int o = 0; o < eo[i]; o++)
				if (!contains(o + 1 == eo[i] ? i : ej[i][o + 1], ej[i][o])) {
					ans[i] = 0;
					break;
				}
		}
	return ans;
}

Compilation message

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

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 0 ms 2392 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2396 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Incorrect 1 ms 2392 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
21 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 52 ms 13660 KB Output is correct
8 Correct 49 ms 13508 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 53 ms 13512 KB Output is correct
18 Correct 70 ms 13564 KB Output is correct
19 Correct 63 ms 13532 KB Output is correct
20 Correct 66 ms 13648 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2488 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2652 KB Output is correct
15 Correct 27 ms 9308 KB Output is correct
16 Correct 27 ms 8796 KB Output is correct
17 Correct 27 ms 9048 KB Output is correct
18 Correct 30 ms 9052 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 52 ms 13660 KB Output is correct
6 Correct 49 ms 13508 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 57 ms 15632 KB Output is correct
12 Correct 53 ms 14676 KB Output is correct

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2392 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 1 ms 2392 KB Output is correct
23 Incorrect 1 ms 2392 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Incorrect 1 ms 2392 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2392 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 1 ms 2392 KB Output is correct
23 Incorrect 1 ms 2392 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2392 KB Output is correct
2 Correct 0 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 0 ms 2392 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Incorrect 1 ms 2392 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
17 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 0 ms 2392 KB Output is correct
5 Correct 0 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 0 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 0 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 0 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 0 ms 2392 KB Output is correct
19 Correct 0 ms 2396 KB Output is correct
20 Correct 0 ms 2396 KB Output is correct
21 Correct 0 ms 2396 KB Output is correct
22 Correct 1 ms 2392 KB Output is correct
23 Incorrect 1 ms 2392 KB 2nd lines differ - on the 1st token, expected: '1', found: '0'
24 Halted 0 ms 0 KB -