oj.uz

Submission #537772

# Submission time Handle Problem Language Result Execution time Memory
537772 2022-03-15T13:36:24 Z rainboy 한자 끝말잇기 (JOI14_kanji) C
100 / 100
 170 ms 19192 KB 
#include "Annalib.h"

#define N	300
#define C	5
#define INF	0x3f3f3f3f3f3f3f3fLL

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

void Anna(int n, int m, int *uu, int *vv, long long *ww, int q, int *ss, int *tt, int c, int *hh) {
	long long ww_[N][N], dd_[N][N], xx_[C + 1][C + 1], dd1[C + 1], dd2[C + 1], ee[C + 1];
	int hh_[C + 1][C + 1], pp[C + 1];
	int g, g_, g1, g2, h, h_, i, j, k, u, v;

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			ww_[i][j] = INF;
	for (h = 0; h < m; h++) {
		u = uu[h], v = vv[h];
		ww_[u][v] = ww[h];
	}
	for (g = 0; g < c; g++) {
		h = hh[g], u = uu[h], v = vv[h];
		ww_[u][v] = INF;
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			dd_[i][j] = i == j ? 0 : ww_[i][j];
	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				dd_[i][j] = min(dd_[i][j], dd_[i][k] + dd_[k][j]);
	for (g1 = 0; g1 <= c; g1++)
		for (g2 = 0; g2 <= c; g2++)
			xx_[g1][g2] = -INF, hh_[g1][g2] = -1;
	for (h = 0; h < q; h++) {
		i = ss[h], j = tt[h];
		for (g = 0; g < c; g++) {
			h_ = hh[g], u = uu[h_], v = vv[h_];
			dd1[g] = min(dd_[i][u] + dd_[v][j], INF), dd2[g] = min(dd1[g] + ww[h_], INF);
		}
		dd1[c] = dd2[c] = dd_[i][j];
		g_ = -1;
		for (g = 0; g <= c; g++)
			if (g_ == -1 || dd2[g_] > dd2[g])
				g_ = g;
		for (g = 0; g <= c; g++)
			if (dd2[g] > dd2[g_]) {
				long long x = dd1[g_] - dd1[g] + 1;

				if (xx_[g_][g] < x)
					xx_[g_][g] = x, hh_[g_][g] = h;
			}
	}
	for (g = 0; g <= c; g++)
		ee[g] = 0, pp[g] = -1;
	while (1) {
		int updated;
		long long e;

		updated = 0;
		for (g1 = 0; g1 <= c; g1++)
			for (g2 = 0; g2 <= c; g2++)
				if (ee[g2] < (e = ee[g1] + xx_[g1][g2]))
					ee[g2] = e, pp[g2] = g1, updated = 1;
		if (!updated)
			break;
	}
	for (g = 0; g < c; g++) {
		int p = pp[g], f = p == -1 ? -1 : hh_[p][g], t;

		if (p == -1)
			p = c + 1;
		if (f == -1)
			f = q;
		for (t = 0; t < 3; t++)
			Tap(p >> t & 1);
		for (t = 0; t < 6; t++)
			Tap(f >> t & 1);
	}
}
#include "Brunolib.h"

#define N	300
#define Q	60
#define C	5
#define INF	0x3f3f3f3f3f3f3f3fLL

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

static long long weight(long long xx[][C + 1][C + 1], int *pp, int *ff, int g) {
	return pp[g] == -1 ? 0 : weight(xx, pp, ff, pp[g]) + (ff[g] == -1 ? -INF : xx[ff[g]][pp[g]][g]);
}

static void print(long long dd[][N], long long ww[][N], int hh[][N], int n, int i, int j) {
	int k;

	if (i == j)
		return;
	for (k = 0; k < n; k++)
		if (dd[i][k] + ww[k][j] == dd[i][j]) {
			print(dd, ww, hh, n, i, k), Answer(hh[k][j]);
			return;
		}
}

void Bruno(int n, int m, int *uu, int *vv, long long *ww, int q, int *ss, int *tt, int c, int *hh, int len, int *buf) {
	long long ww_[N][N], dd_[N][N], xx_[Q][C + 1][C + 1], dd1[C + 1], ee[C + 1];
	int hh_[N][N], pp[C + 1], ff[C + 1];
	int g, g1, g2, h, h_, i, j, k, u, v;

	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			ww_[i][j] = INF;
	for (h = 0; h < m; h++) {
		u = uu[h], v = vv[h];
		ww_[u][v] = ww[h], hh_[u][v] = h;
	}
	for (g = 0; g < c; g++) {
		h = hh[g], u = uu[h], v = vv[h];
		ww_[u][v] = INF;
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			dd_[i][j] = i == j ? 0 : ww_[i][j];
	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				dd_[i][j] = min(dd_[i][j], dd_[i][k] + dd_[k][j]);
	for (h = 0; h < q; h++) {
		i = ss[h], j = tt[h];
		for (g = 0; g < c; g++) {
			h_ = hh[g], u = uu[h_], v = vv[h_];
			dd1[g] = min(dd_[i][u] + dd_[v][j], INF);
		}
		dd1[c] = dd_[i][j];
		for (g1 = 0; g1 <= c; g1++)
			for (g2 = 0; g2 <= c; g2++)
				xx_[h][g1][g2] = dd1[g1] - dd1[g2] + 1;
	}
	pp[c] = -1, ff[c] = -1;
	for (g = 0; g < c; g++) {
		int t;

		pp[g] = 0;
		for (t = 0; t < 3; t++)
			if (buf[g * 9 + t])
				pp[g] |= 1 << t;
		ff[g] = 0;
		for (t = 0; t < 6; t++)
			if (buf[g * 9 + 3 + t])
				ff[g] |= 1 << t;
		if (pp[g] == c + 1)
			pp[g] = -1;
		if (ff[g] == q)
			ff[g] = -1;
	}
	for (g = 0; g < c; g++)
		ee[g] = weight(xx_, pp, ff, g);
	for (g = 0; g < c; g++) {
		h = hh[g], u = uu[h], v = vv[h];
		ww_[u][v] = ee[g];
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			dd_[i][j] = i == j ? 0 : ww_[i][j];
	for (k = 0; k < n; k++)
		for (i = 0; i < n; i++)
			for (j = 0; j < n; j++)
				dd_[i][j] = min(dd_[i][j], dd_[i][k] + dd_[k][j]);
	for (h = 0; h < q; h++) {
		i = ss[h], j = tt[h];
		print(dd_, ww_, hh_, n, i, j), Answer(-1);
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7308 KB Output is correct - L = 45
2 Correct 91 ms 7500 KB Output is correct - L = 45
3 Correct 85 ms 7460 KB Output is correct - L = 45
4 Correct 87 ms 7236 KB Output is correct - L = 45
5 Correct 89 ms 7408 KB Output is correct - L = 45
6 Correct 96 ms 7416 KB Output is correct - L = 45
7 Correct 89 ms 7288 KB Output is correct - L = 45
8 Correct 90 ms 7456 KB Output is correct - L = 45
9 Correct 104 ms 7700 KB Output is correct - L = 45
10 Correct 96 ms 7860 KB Output is correct - L = 45
11 Correct 95 ms 7348 KB Output is correct - L = 45
12 Correct 163 ms 17104 KB Output is correct - L = 45
13 Correct 96 ms 7488 KB Output is correct - L = 45
14 Correct 102 ms 7332 KB Output is correct - L = 9

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7644 KB Output is correct - L = 45
2 Correct 88 ms 7584 KB Output is correct - L = 45
3 Correct 91 ms 7684 KB Output is correct - L = 45
4 Correct 87 ms 7692 KB Output is correct - L = 45
5 Correct 88 ms 7456 KB Output is correct - L = 45
6 Correct 91 ms 7700 KB Output is correct - L = 45
7 Correct 90 ms 7680 KB Output is correct - L = 45
8 Correct 90 ms 7704 KB Output is correct - L = 45
9 Correct 92 ms 7808 KB Output is correct - L = 45
10 Correct 107 ms 7744 KB Output is correct - L = 45
11 Correct 84 ms 7628 KB Output is correct - L = 45
12 Correct 88 ms 7668 KB Output is correct - L = 45
13 Correct 170 ms 18944 KB Output is correct - L = 45
14 Correct 91 ms 7716 KB Output is correct - L = 45
15 Correct 87 ms 7708 KB Output is correct - L = 45
16 Correct 92 ms 7784 KB Output is correct - L = 45
17 Correct 94 ms 7960 KB Output is correct - L = 45
18 Correct 98 ms 8488 KB Output is correct - L = 45
19 Correct 87 ms 7484 KB Output is correct - L = 45
20 Correct 93 ms 8936 KB Output is correct - L = 45
21 Correct 98 ms 8848 KB Output is correct - L = 45
22 Correct 88 ms 7916 KB Output is correct - L = 45
23 Correct 90 ms 7724 KB Output is correct - L = 45
24 Correct 92 ms 7708 KB Output is correct - L = 45

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7664 KB Output is correct - L = 45
2 Correct 86 ms 7580 KB Output is correct - L = 45
3 Correct 89 ms 7616 KB Output is correct - L = 45
4 Correct 89 ms 7704 KB Output is correct - L = 45
5 Correct 94 ms 7456 KB Output is correct - L = 45
6 Correct 92 ms 7696 KB Output is correct - L = 45
7 Correct 95 ms 7756 KB Output is correct - L = 45
8 Correct 88 ms 7716 KB Output is correct - L = 45
9 Correct 95 ms 7948 KB Output is correct - L = 45
10 Correct 95 ms 7700 KB Output is correct - L = 45
11 Correct 88 ms 7836 KB Output is correct - L = 45
12 Correct 84 ms 7752 KB Output is correct - L = 45
13 Correct 162 ms 19120 KB Output is correct - L = 45
14 Correct 87 ms 7648 KB Output is correct - L = 45
15 Correct 94 ms 7760 KB Output is correct - L = 45
16 Correct 86 ms 7832 KB Output is correct - L = 45
17 Correct 86 ms 7896 KB Output is correct - L = 45
18 Correct 95 ms 8540 KB Output is correct - L = 45
19 Correct 90 ms 7416 KB Output is correct - L = 45
20 Correct 99 ms 8940 KB Output is correct - L = 45
21 Correct 96 ms 8896 KB Output is correct - L = 45
22 Correct 90 ms 7772 KB Output is correct - L = 45
23 Correct 86 ms 7716 KB Output is correct - L = 45
24 Correct 92 ms 7776 KB Output is correct - L = 45

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 7640 KB Output is correct - L = 45
2 Correct 86 ms 7700 KB Output is correct - L = 45
3 Correct 89 ms 7680 KB Output is correct - L = 45
4 Correct 96 ms 7716 KB Output is correct - L = 45
5 Correct 84 ms 7444 KB Output is correct - L = 45
6 Correct 88 ms 7728 KB Output is correct - L = 45
7 Correct 92 ms 7768 KB Output is correct - L = 45
8 Correct 87 ms 7740 KB Output is correct - L = 45
9 Correct 86 ms 7848 KB Output is correct - L = 45
10 Correct 89 ms 7736 KB Output is correct - L = 45
11 Correct 89 ms 7728 KB Output is correct - L = 45
12 Correct 90 ms 7648 KB Output is correct - L = 45
13 Correct 161 ms 19192 KB Output is correct - L = 45
14 Correct 90 ms 7704 KB Output is correct - L = 45
15 Correct 95 ms 7744 KB Output is correct - L = 45
16 Correct 90 ms 7872 KB Output is correct - L = 45
17 Correct 89 ms 7892 KB Output is correct - L = 45
18 Correct 98 ms 8524 KB Output is correct - L = 45
19 Correct 88 ms 7372 KB Output is correct - L = 45
20 Correct 92 ms 8932 KB Output is correct - L = 45
21 Correct 96 ms 8960 KB Output is correct - L = 45
22 Correct 92 ms 7708 KB Output is correct - L = 45
23 Correct 90 ms 7680 KB Output is correct - L = 45
24 Correct 87 ms 7732 KB Output is correct - L = 45

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7656 KB Output is correct - L = 45
2 Correct 96 ms 7604 KB Output is correct - L = 45
3 Correct 88 ms 7648 KB Output is correct - L = 45
4 Correct 89 ms 7676 KB Output is correct - L = 45
5 Correct 91 ms 7336 KB Output is correct - L = 45
6 Correct 94 ms 7664 KB Output is correct - L = 45
7 Correct 98 ms 7696 KB Output is correct - L = 45
8 Correct 88 ms 7632 KB Output is correct - L = 45
9 Correct 89 ms 7824 KB Output is correct - L = 45
10 Correct 96 ms 7704 KB Output is correct - L = 45
11 Correct 87 ms 7704 KB Output is correct - L = 45
12 Correct 91 ms 7704 KB Output is correct - L = 45
13 Correct 167 ms 14656 KB Output is correct - L = 45
14 Correct 86 ms 7696 KB Output is correct - L = 45
15 Correct 86 ms 7700 KB Output is correct - L = 45
16 Correct 91 ms 7736 KB Output is correct - L = 45
17 Correct 96 ms 7796 KB Output is correct - L = 45
18 Correct 102 ms 8100 KB Output is correct - L = 45
19 Correct 84 ms 7320 KB Output is correct - L = 45
20 Correct 95 ms 8392 KB Output is correct - L = 45
21 Correct 93 ms 8416 KB Output is correct - L = 45
22 Correct 99 ms 7696 KB Output is correct - L = 45
23 Correct 93 ms 7728 KB Output is correct - L = 45
24 Correct 85 ms 7624 KB Output is correct - L = 45