oj.uz

Submission #537770

# Submission time Handle Problem Language Result Execution time Memory
537770 2022-03-15T13:35:37 Z rainboy 한자 끝말잇기 (JOI14_kanji) C
0 / 100
 88 ms 14916 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 (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			printf("%lld ", dd_[i][j]);
		printf("\n");
	}
	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);
	}
}

Compilation message

Anna.c: In function 'Anna':
Anna.c:37:4: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
   37 |    printf("%lld ", dd_[i][j]);
      |    ^~~~~~
Anna.c:37:4: warning: incompatible implicit declaration of built-in function 'printf'
Anna.c:2:1: note: include '<stdio.h>' or provide a declaration of 'printf'
    1 | #include "Annalib.h"
  +++ |+#include <stdio.h>
    2 | 
Anna.c:38:3: warning: incompatible implicit declaration of built-in function 'printf'
   38 |   printf("\n");
      |   ^~~~~~
Anna.c:38:3: note: include '<stdio.h>' or provide a declaration of 'printf'

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 7120 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 7312 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 7352 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 7364 KB Do not print anything to standard output
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 7360 KB Do not print anything to standard output
2 Incorrect 44 ms 7200 KB Do not print anything to standard output
3 Incorrect 55 ms 7308 KB Do not print anything to standard output
4 Incorrect 45 ms 7224 KB Do not print anything to standard output
5 Incorrect 45 ms 7184 KB Do not print anything to standard output
6 Incorrect 39 ms 7320 KB Do not print anything to standard output
7 Incorrect 40 ms 7252 KB Do not print anything to standard output
8 Incorrect 39 ms 7332 KB Do not print anything to standard output
9 Incorrect 40 ms 7412 KB Do not print anything to standard output
10 Incorrect 49 ms 7624 KB Do not print anything to standard output
11 Incorrect 45 ms 7560 KB Do not print anything to standard output
12 Incorrect 44 ms 7496 KB Do not print anything to standard output
13 Incorrect 88 ms 14916 KB Do not print anything to standard output
14 Incorrect 42 ms 7352 KB Do not print anything to standard output
15 Incorrect 41 ms 7332 KB Do not print anything to standard output
16 Incorrect 43 ms 7340 KB Do not print anything to standard output
17 Incorrect 45 ms 7664 KB Do not print anything to standard output
18 Incorrect 44 ms 7848 KB Do not print anything to standard output
19 Incorrect 40 ms 7204 KB Do not print anything to standard output
20 Incorrect 47 ms 8252 KB Do not print anything to standard output
21 Incorrect 48 ms 7992 KB Do not print anything to standard output
22 Incorrect 48 ms 7432 KB Do not print anything to standard output
23 Incorrect 39 ms 7420 KB Do not print anything to standard output
24 Incorrect 44 ms 7676 KB Do not print anything to standard output