oj.uz

Submission #711376

# Submission time Handle Problem Language Result Execution time Memory
711376 2023-03-16T18:26:49 Z rainboy Amusement Park (JOI17_amusement_park) C++14
100 / 100
 45 ms 19092 KB 
#include "Joi.h"
#include <stdlib.h>
#include <string.h>
 
static const int N = 10000, L = 60;
 
static int *ej[N], eo[N], ii_[N][L], uu_[N][L], vv_[N][L];
 
static 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;
}
 
static int cc[N], n_, m_;
 
static bool dfs1(int i) {
	ii_[0][cc[i] = n_++] = i;
	if (n_ == L)
		return true;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			bool done = dfs1(j);
			uu_[0][m_] = cc[i], vv_[0][m_] = cc[j], m_++;
			if (done)
				return true;
		}
	}
	return false;
}
 
static int dd[L];
 
static void extend(int i, int j) {
	memset(dd, 0, L * sizeof *dd);
	memcpy(ii_[j], ii_[i], L * sizeof *ii_[i]);
	memcpy(uu_[j], uu_[i], (L - 1) * sizeof *uu_[i]);
	memcpy(vv_[j], vv_[i], (L - 1) * sizeof *vv_[i]);
	for (int h = 0; h < L - 1; h++) {
		int u = uu_[j][h], v = vv_[j][h];
		dd[u]++, dd[v]++;
	}
	int a = cc[i];
	for (int b = 0; b < L; b++)
		if (b != cc[i] && dd[b] == 1) {
			ii_[j][cc[j] = b] = j;
			for (int h = 0; h < L - 1; h++) {
				int u = uu_[j][h], v = vv_[j][h];
				if (u == b || v == b) {
					uu_[j][h] = a, vv_[j][h] = b;
					return;
				}
			}
		}
}
 
static void dfs2(int i) {
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			extend(i, j);
			dfs2(j);
		}
	}
}
 
static void alloc_(int n) {
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
}
 
static void free_(int n) {
	for (int i = 0; i < n; i++)
		free(ej[i]);
}
 
static void precalc(int *uu, int *vv, int n, int m) {
	for (int h = 0; h < m; h++)
		append(uu[h], vv[h]), append(vv[h], uu[h]);
	memset(cc, -1, n * sizeof *cc);
	n_ = 0, m_ = 0, dfs1(0);
	for (int a = 1; a < L; a++) {
		int i = ii_[0][a];
		memcpy(ii_[i], ii_[0], L * sizeof *ii_[0]);
		memcpy(uu_[i], uu_[0], (L - 1) * sizeof *uu_[0]);
		memcpy(vv_[i], vv_[0], (L - 1) * sizeof *vv_[0]);
	}
	for (int a = 0; a < L; a++) {
		int i = ii_[0][a];
		dfs2(i);
	}
}
 
void Joi(int n, int m, int *uu, int *vv, long long x, int t) {
	t = t;
	alloc_(n);
	precalc(uu, vv, n, m);
	for (int i = 0; i < n; i++)
		MessageBoard(i, x >> cc[i] & 1);
	free_(n);
}
#include "Ioi.h"
#include <stdlib.h>
#include <string.h>

static const int N = 10000, L = 60;

static int *ej[N], eo[N], ii_[N][L], uu_[N][L], vv_[N][L];

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

static int cc[N], n_, m_;

static bool dfs1(int i) {
	ii_[0][cc[i] = n_++] = i;
	if (n_ == L)
		return true;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			bool done = dfs1(j);
			uu_[0][m_] = cc[i], vv_[0][m_] = cc[j], m_++;
			if (done)
				return true;
		}
	}
	return false;
}

static int dd[L];

static void extend(int i, int j) {
	memset(dd, 0, L * sizeof *dd);
	memcpy(ii_[j], ii_[i], L * sizeof *ii_[i]);
	memcpy(uu_[j], uu_[i], (L - 1) * sizeof *uu_[i]);
	memcpy(vv_[j], vv_[i], (L - 1) * sizeof *vv_[i]);
	for (int h = 0; h < L - 1; h++) {
		int u = uu_[j][h], v = vv_[j][h];
		dd[u]++, dd[v]++;
	}
	int a = cc[i];
	for (int b = 0; b < L; b++)
		if (b != cc[i] && dd[b] == 1) {
			ii_[j][cc[j] = b] = j;
			for (int h = 0; h < L - 1; h++) {
				int u = uu_[j][h], v = vv_[j][h];
				if (u == b || v == b) {
					uu_[j][h] = a, vv_[j][h] = b;
					return;
				}
			}
		}
}

static void dfs2(int i) {
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			extend(i, j);
			dfs2(j);
		}
	}
}

static void alloc_(int n) {
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
}

static void free_(int n) {
	for (int i = 0; i < n; i++)
		free(ej[i]);
}

static void precalc(int *uu, int *vv, int n, int m) {
	for (int h = 0; h < m; h++)
		append(uu[h], vv[h]), append(vv[h], uu[h]);
	memset(cc, -1, n * sizeof *cc);
	n_ = 0, m_ = 0, dfs1(0);
	for (int a = 1; a < L; a++) {
		int i = ii_[0][a];
		memcpy(ii_[i], ii_[0], L * sizeof *ii_[0]);
		memcpy(uu_[i], uu_[0], (L - 1) * sizeof *uu_[0]);
		memcpy(vv_[i], vv_[0], (L - 1) * sizeof *vv_[0]);
	}
	for (int a = 0; a < L; a++) {
		int i = ii_[0][a];
		dfs2(i);
	}
}

static long long x;

static void dfs3(int p, int i, int z) {
	x |= (long long) z << cc[i];
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p)
			dfs3(i, j, Move(j)), Move(i);
	}
}

long long Ioi(int n, int m, int *uu, int *vv, int s, int z, int t) {
	t = t;
	alloc_(n);
	precalc(uu, vv, n, m);
	free_(n);
	alloc_(n);
	for (int h = 0; h < L - 1; h++) {
		int u = uu_[s][h], v = vv_[s][h], u_ = ii_[s][u], v_ = ii_[s][v];
		append(u_, v_), append(v_, u_);
	}
	x = 0;
	dfs3(-1, s, z);
	return x;
}

Compilation message

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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 780 KB Output is correct
2 Correct 0 ms 916 KB Output is correct
3 Correct 1 ms 1048 KB Output is correct
4 Correct 0 ms 788 KB Output is correct
5 Correct 1 ms 780 KB Output is correct
6 Correct 2 ms 1036 KB Output is correct
7 Correct 2 ms 1168 KB Output is correct
8 Correct 1 ms 1040 KB Output is correct
9 Correct 2 ms 1048 KB Output is correct
10 Correct 0 ms 780 KB Output is correct
11 Correct 3 ms 1212 KB Output is correct
12 Correct 0 ms 788 KB Output is correct
13 Correct 1 ms 1040 KB Output is correct
14 Correct 2 ms 1040 KB Output is correct
15 Correct 2 ms 1048 KB Output is correct
16 Correct 2 ms 1040 KB Output is correct
17 Correct 1 ms 1048 KB Output is correct
18 Correct 2 ms 1048 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18496 KB Output is correct
2 Correct 45 ms 18876 KB Output is correct
3 Correct 35 ms 18908 KB Output is correct
4 Correct 24 ms 16716 KB Output is correct
5 Correct 27 ms 17524 KB Output is correct
6 Correct 27 ms 17236 KB Output is correct
7 Correct 26 ms 17340 KB Output is correct
8 Correct 27 ms 17400 KB Output is correct
9 Correct 28 ms 17508 KB Output is correct
10 Correct 28 ms 16616 KB Output is correct
11 Correct 26 ms 16772 KB Output is correct
12 Correct 23 ms 15156 KB Output is correct
13 Correct 25 ms 15176 KB Output is correct
14 Correct 25 ms 15888 KB Output is correct
15 Correct 27 ms 16540 KB Output is correct
16 Correct 33 ms 16504 KB Output is correct
17 Correct 26 ms 16620 KB Output is correct
18 Correct 25 ms 16672 KB Output is correct
19 Correct 25 ms 16664 KB Output is correct
20 Correct 23 ms 17644 KB Output is correct
21 Correct 22 ms 17436 KB Output is correct
22 Correct 27 ms 17128 KB Output is correct
23 Correct 33 ms 17356 KB Output is correct
24 Correct 29 ms 17076 KB Output is correct
25 Correct 27 ms 17380 KB Output is correct
26 Correct 27 ms 17440 KB Output is correct
27 Correct 27 ms 17456 KB Output is correct
28 Correct 27 ms 17624 KB Output is correct
29 Correct 25 ms 15888 KB Output is correct
30 Correct 27 ms 16496 KB Output is correct
31 Correct 2 ms 920 KB Output is correct
32 Correct 1 ms 888 KB Output is correct
33 Correct 2 ms 1052 KB Output is correct
34 Correct 1 ms 912 KB Output is correct
35 Correct 1 ms 784 KB Output is correct
36 Correct 1 ms 784 KB Output is correct
37 Correct 1 ms 764 KB Output is correct
38 Correct 0 ms 784 KB Output is correct
39 Correct 2 ms 752 KB Output is correct
40 Correct 1 ms 788 KB Output is correct
41 Correct 1 ms 792 KB Output is correct
42 Correct 2 ms 776 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 788 KB Output is correct
2 Correct 0 ms 788 KB Output is correct
3 Correct 0 ms 788 KB Output is correct
4 Correct 4 ms 3624 KB Output is correct
5 Correct 4 ms 3632 KB Output is correct
6 Correct 5 ms 3508 KB Output is correct
7 Correct 6 ms 3592 KB Output is correct
8 Correct 5 ms 3632 KB Output is correct
9 Correct 23 ms 18568 KB Output is correct
10 Correct 22 ms 18568 KB Output is correct
11 Correct 25 ms 18568 KB Output is correct
12 Correct 1 ms 736 KB Output is correct
13 Correct 0 ms 784 KB Output is correct
14 Correct 1 ms 792 KB Output is correct
15 Correct 0 ms 740 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 18484 KB Output is correct
2 Correct 35 ms 18952 KB Output is correct
3 Correct 38 ms 18952 KB Output is correct
4 Correct 27 ms 16672 KB Output is correct
5 Correct 27 ms 18044 KB Output is correct
6 Correct 27 ms 17496 KB Output is correct
7 Correct 29 ms 17376 KB Output is correct
8 Correct 30 ms 16984 KB Output is correct
9 Correct 27 ms 17104 KB Output is correct
10 Correct 28 ms 16660 KB Output is correct
11 Correct 25 ms 16616 KB Output is correct
12 Correct 23 ms 15160 KB Output is correct
13 Correct 24 ms 15096 KB Output is correct
14 Correct 30 ms 15864 KB Output is correct
15 Correct 35 ms 16516 KB Output is correct
16 Correct 25 ms 16544 KB Output is correct
17 Correct 26 ms 16660 KB Output is correct
18 Correct 26 ms 16672 KB Output is correct
19 Correct 27 ms 16648 KB Output is correct
20 Correct 25 ms 17684 KB Output is correct
21 Correct 23 ms 17460 KB Output is correct
22 Correct 28 ms 17364 KB Output is correct
23 Correct 28 ms 17232 KB Output is correct
24 Correct 27 ms 17188 KB Output is correct
25 Correct 27 ms 17400 KB Output is correct
26 Correct 27 ms 17428 KB Output is correct
27 Correct 26 ms 17552 KB Output is correct
28 Correct 28 ms 17120 KB Output is correct
29 Correct 28 ms 15784 KB Output is correct
30 Correct 28 ms 16612 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 18504 KB Output is correct
2 Correct 38 ms 19008 KB Output is correct
3 Correct 38 ms 19092 KB Output is correct
4 Correct 28 ms 16668 KB Output is correct
5 Correct 33 ms 18264 KB Output is correct
6 Correct 28 ms 17228 KB Output is correct
7 Correct 27 ms 17108 KB Output is correct
8 Correct 28 ms 17408 KB Output is correct
9 Correct 26 ms 17296 KB Output is correct
10 Correct 25 ms 16644 KB Output is correct
11 Correct 31 ms 16664 KB Output is correct
12 Correct 28 ms 15036 KB Output is correct
13 Correct 24 ms 15180 KB Output is correct
14 Correct 24 ms 15896 KB Output is correct
15 Correct 25 ms 16544 KB Output is correct
16 Correct 31 ms 16404 KB Output is correct
17 Correct 28 ms 16656 KB Output is correct
18 Correct 28 ms 16648 KB Output is correct
19 Correct 27 ms 16692 KB Output is correct
20 Correct 26 ms 17704 KB Output is correct
21 Correct 26 ms 17408 KB Output is correct
22 Correct 27 ms 17400 KB Output is correct
23 Correct 28 ms 17228 KB Output is correct
24 Correct 27 ms 17108 KB Output is correct
25 Correct 28 ms 17280 KB Output is correct
26 Correct 27 ms 17184 KB Output is correct
27 Correct 30 ms 17476 KB Output is correct
28 Correct 27 ms 17576 KB Output is correct
29 Correct 25 ms 16104 KB Output is correct
30 Correct 25 ms 16620 KB Output is correct
31 Correct 1 ms 788 KB Output is correct
32 Correct 1 ms 1048 KB Output is correct
33 Correct 2 ms 1044 KB Output is correct
34 Correct 1 ms 816 KB Output is correct
35 Correct 1 ms 800 KB Output is correct
36 Correct 1 ms 740 KB Output is correct
37 Correct 1 ms 784 KB Output is correct
38 Correct 1 ms 792 KB Output is correct
39 Correct 0 ms 784 KB Output is correct
40 Correct 1 ms 760 KB Output is correct
41 Correct 1 ms 800 KB Output is correct
42 Correct 1 ms 776 KB Output is correct