oj.uz

Submission #711368

# Submission time Handle Problem Language Result Execution time Memory
711368 2023-03-16T18:07:25 Z rainboy Amusement Park (JOI17_amusement_park) C++14
8 / 100
 37 ms 19200 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 - 1; 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 - 1; 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 1 ms 784 KB Output is correct
2 Correct 1 ms 888 KB Output is correct
3 Correct 1 ms 1044 KB Output is correct
4 Correct 1 ms 788 KB Output is correct
5 Correct 1 ms 792 KB Output is correct
6 Correct 1 ms 912 KB Output is correct
7 Correct 2 ms 1168 KB Output is correct
8 Correct 2 ms 1144 KB Output is correct
9 Correct 2 ms 1044 KB Output is correct
10 Correct 1 ms 868 KB Output is correct
11 Correct 4 ms 1248 KB Output is correct
12 Correct 1 ms 744 KB Output is correct
13 Correct 2 ms 1040 KB Output is correct
14 Correct 1 ms 1048 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 2 ms 1128 KB Output is correct
17 Correct 2 ms 1076 KB Output is correct
18 Correct 2 ms 1148 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 19200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 784 KB Output is correct
2 Correct 1 ms 792 KB Output is correct
3 Correct 1 ms 792 KB Output is correct
4 Correct 5 ms 3640 KB Output is correct
5 Incorrect 5 ms 3516 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 18904 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 18868 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -