oj.uz

Submission #6152

# Submission time Handle Problem Language Result Execution time Memory
6152 2014-06-20T16:59:45 Z ainta 한자 끝말잇기 (JOI14_kanji) C++
100 / 100
 825 ms 92964 KB 
#include "Annalib.h"
#define ull unsigned long long
#define INF 4000000000000000000LL
ull w[301][301];
bool v[90010];
int R[61], cnt[5];
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
	int i, j, k, x, y, xx, yy;
	ull g;
	for (i = 0; i < K; i++){
		v[U[i]] = true;
	}
	for (i = 0; i < Q; i++)R[i] = -1;
	for (i = 0; i < N; i++){
		for (j = 0; j < N; j++){
			if (i != j)w[i][j] = INF;
			else w[i][j] = 0;
		}
	}
	for (i = 0; i < M; i++){
		if (!v[i])w[A[i]][B[i]] = C[i];
	}
	for (k = 0; k < N; k++){
		for (i = 0; i < N; i++){
			for (j = 0; j < N; j++){
				if (w[i][j]>w[i][k] + w[k][j])w[i][j] = w[i][k] + w[k][j];
			}
		}
	}
	for (i = 0; i < K; i++){
		x = A[U[i]], y = B[U[i]];
		for (j = 0; j < Q; j++){
			xx = S[j], yy = T[j];
			g = w[xx][x] + w[y][yy] + C[U[i]];
			if (w[xx][yy]>g){
				w[xx][yy] = g;
				R[j] = i;
			}
		}
	}
	for (i = 0; i < Q; i++){
		if (R[i] != -1)cnt[R[i]]++;
	}
	for (i = 0; i < K; i++){
		for (j = 0; j < 6; j++){
			if ((1 << j)&cnt[i])Tap(1);
			else Tap(0);
		}
	}
}

#include "Brunolib.h"
#define ull unsigned long long
#define INF 4000000000000000000LL
ull w[310][310], w3[310][310];
int w2[310][310];
ull P[5][60];
ull D[321293][2], G[6], cnt[6];
int par[60][321293], Res[60];
int n;
void Do(int a, int b)
{
	int i;
	ull gap = w[a][b];
	while (1){
		if (a == b)break;
		for (i = 0; i < n; i++){
			if (a != i && w2[a][i]&& w3[a][i] + w[i][b] == gap)break;
		}
		gap -= w3[a][i];
		Answer(w2[a][i] - 1);
		a = i;
	}
}
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]) {
	n = N;
	int i, j, k, x, y;
	ull t1, t2, t3;
	for (i = 0; i < N; i++){
		for (j = 0; j < N; j++){
			if (i != j)w[i][j] = INF;
			else w[i][j] = 0;
		}
	}
	for (i = 0; i < M; i++){
		if (C[i] != -1){
			w[A[i]][B[i]] = C[i];
		}
		w2[A[i]][B[i]] = i + 1;
		w3[A[i]][B[i]] = C[i];
	}
	for (k = 0; k < N; k++){
		for (i = 0; i < N; i++){
			for (j = 0; j < N; j++){
				if (w[i][j]>w[i][k] + w[k][j])w[i][j] = w[i][k] + w[k][j];
			}
		}
	}
	for (i = 0; i < K; i++){
		for (j = 0; j < Q; j++){
			t1 = w[S[j]][T[j]];
			t2 = w[S[j]][A[U[i]]];
			t3 = w[B[U[i]]][T[j]];
			if (t2 == INF || t3 == INF)continue;
			if (t2 + t3 >= t1)continue;
			P[i][j] = t1 - t2 - t3;
		}
	}
	G[0] = 1;
	for (i = 0; i < K; i++){
		for (j = 0; j < 6; j++){
			if (X[i * 6 + j])cnt[i] += (1 << j);
		}
		G[i + 1] = G[i] * (cnt[i] + 1);
	}
	for (i = 0; i < Q; i++){
		for (j = 0; j < G[K]; j++)par[i][j] = -1;
		for (j = G[K] - 1; j >= 0; j--){
			if (j && (!D[j][0] && !D[j][1]))continue;
			for (k = 0; k < K; k++){
				if (!P[k][i])continue;
				if ((j % G[k + 1]) / G[k] == cnt[k])continue;
				t1 = D[j][0];
				t2 = P[k][i] + D[j][1];
				t1 += t2 >> 40, t2 &= ((1ll << 40) - 1);
				if (D[j + G[k]][0] < t1 || (D[j + G[k]][0] == t1&&D[j + G[k]][1] < t2)){
					D[j + G[k]][0] = t1;
					D[j + G[k]][1] = t2;
					par[i][j + G[k]] = k;
				}
			}
		}
	}
	x = G[K] - 1, y = Q - 1;
	for (i = 0; i < Q; i++)Res[i] = -1;
	while (x){
		if (par[y][x] == -1){
			y--;
			continue;
		}
		Res[y] = par[y][x];
		x -= G[par[y][x]];
		y--;
	}
	for (i = 0; i < Q; i++){
		if (Res[i] == -1){
			Do(S[i], T[i]);
		}
		else{
			Do(S[i], A[U[Res[i]]]);
			Answer(U[Res[i]]);
			Do(B[U[Res[i]]], T[i]);
		}
		Answer(-1);
	}
}

Compilation message

Bruno.cpp: In function 'void Bruno(int, int, int*, int*, long long int*, int, int*, int*, int, int*, int, int*)':
Bruno.cpp:66:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < G[K]; j++)par[i][j] = -1;
                 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 92964 KB Output is correct - L = 30
2 Correct 78 ms 92964 KB Output is correct - L = 30
3 Correct 66 ms 92964 KB Output is correct - L = 30
4 Correct 72 ms 92964 KB Output is correct - L = 30
5 Correct 75 ms 92964 KB Output is correct - L = 30
6 Correct 72 ms 92964 KB Output is correct - L = 30
7 Correct 66 ms 92964 KB Output is correct - L = 30
8 Correct 75 ms 92964 KB Output is correct - L = 30
9 Correct 102 ms 92964 KB Output is correct - L = 30
10 Correct 86 ms 92964 KB Output is correct - L = 30
11 Correct 76 ms 92964 KB Output is correct - L = 30
12 Correct 212 ms 92964 KB Output is correct - L = 30
13 Correct 62 ms 92964 KB Output is correct - L = 30
14 Correct 52 ms 92964 KB Output is correct - L = 6

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 92964 KB Output is correct - L = 30
2 Correct 205 ms 92964 KB Output is correct - L = 30
3 Correct 66 ms 92964 KB Output is correct - L = 30
4 Correct 68 ms 92964 KB Output is correct - L = 30
5 Correct 238 ms 92964 KB Output is correct - L = 30
6 Correct 249 ms 92964 KB Output is correct - L = 30
7 Correct 66 ms 92964 KB Output is correct - L = 30
8 Correct 82 ms 92964 KB Output is correct - L = 30
9 Correct 796 ms 92964 KB Output is correct - L = 30
10 Correct 772 ms 92964 KB Output is correct - L = 30
11 Correct 772 ms 92964 KB Output is correct - L = 30
12 Correct 66 ms 92964 KB Output is correct - L = 30
13 Correct 212 ms 92964 KB Output is correct - L = 30
14 Correct 132 ms 92964 KB Output is correct - L = 30
15 Correct 65 ms 92964 KB Output is correct - L = 30
16 Correct 78 ms 92964 KB Output is correct - L = 30
17 Correct 111 ms 92964 KB Output is correct - L = 30
18 Correct 92 ms 92964 KB Output is correct - L = 30
19 Correct 66 ms 92964 KB Output is correct - L = 30
20 Correct 84 ms 92964 KB Output is correct - L = 30
21 Correct 106 ms 92964 KB Output is correct - L = 30
22 Correct 809 ms 92964 KB Output is correct - L = 30
23 Correct 782 ms 92964 KB Output is correct - L = 30
24 Correct 762 ms 92964 KB Output is correct - L = 30

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 92964 KB Output is correct - L = 30
2 Correct 215 ms 92964 KB Output is correct - L = 30
3 Correct 59 ms 92964 KB Output is correct - L = 30
4 Correct 62 ms 92964 KB Output is correct - L = 30
5 Correct 238 ms 92964 KB Output is correct - L = 30
6 Correct 208 ms 92964 KB Output is correct - L = 30
7 Correct 69 ms 92964 KB Output is correct - L = 30
8 Correct 62 ms 92964 KB Output is correct - L = 30
9 Correct 812 ms 92964 KB Output is correct - L = 30
10 Correct 786 ms 92964 KB Output is correct - L = 30
11 Correct 775 ms 92964 KB Output is correct - L = 30
12 Correct 62 ms 92964 KB Output is correct - L = 30
13 Correct 216 ms 92964 KB Output is correct - L = 30
14 Correct 132 ms 92964 KB Output is correct - L = 30
15 Correct 58 ms 92964 KB Output is correct - L = 30
16 Correct 89 ms 92964 KB Output is correct - L = 30
17 Correct 99 ms 92964 KB Output is correct - L = 30
18 Correct 95 ms 92964 KB Output is correct - L = 30
19 Correct 62 ms 92964 KB Output is correct - L = 30
20 Correct 75 ms 92964 KB Output is correct - L = 30
21 Correct 95 ms 92964 KB Output is correct - L = 30
22 Correct 772 ms 92964 KB Output is correct - L = 30
23 Correct 789 ms 92964 KB Output is correct - L = 30
24 Correct 768 ms 92964 KB Output is correct - L = 30

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 92964 KB Output is correct - L = 30
2 Correct 192 ms 92964 KB Output is correct - L = 30
3 Correct 66 ms 92964 KB Output is correct - L = 30
4 Correct 52 ms 92964 KB Output is correct - L = 30
5 Correct 236 ms 92964 KB Output is correct - L = 30
6 Correct 212 ms 92964 KB Output is correct - L = 30
7 Correct 62 ms 92964 KB Output is correct - L = 30
8 Correct 69 ms 92964 KB Output is correct - L = 30
9 Correct 805 ms 92964 KB Output is correct - L = 30
10 Correct 812 ms 92964 KB Output is correct - L = 30
11 Correct 792 ms 92964 KB Output is correct - L = 30
12 Correct 69 ms 92964 KB Output is correct - L = 30
13 Correct 235 ms 92964 KB Output is correct - L = 30
14 Correct 132 ms 92964 KB Output is correct - L = 30
15 Correct 86 ms 92964 KB Output is correct - L = 30
16 Correct 84 ms 92964 KB Output is correct - L = 30
17 Correct 81 ms 92964 KB Output is correct - L = 30
18 Correct 99 ms 92964 KB Output is correct - L = 30
19 Correct 69 ms 92964 KB Output is correct - L = 30
20 Correct 81 ms 92964 KB Output is correct - L = 30
21 Correct 89 ms 92964 KB Output is correct - L = 30
22 Correct 795 ms 92964 KB Output is correct - L = 30
23 Correct 782 ms 92964 KB Output is correct - L = 30
24 Correct 779 ms 92964 KB Output is correct - L = 30

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 92964 KB Output is correct - L = 30
2 Correct 205 ms 92964 KB Output is correct - L = 30
3 Correct 62 ms 92964 KB Output is correct - L = 30
4 Correct 58 ms 92964 KB Output is correct - L = 30
5 Correct 238 ms 92964 KB Output is correct - L = 30
6 Correct 222 ms 92964 KB Output is correct - L = 30
7 Correct 62 ms 92964 KB Output is correct - L = 30
8 Correct 81 ms 92964 KB Output is correct - L = 30
9 Correct 825 ms 92964 KB Output is correct - L = 30
10 Correct 769 ms 92964 KB Output is correct - L = 30
11 Correct 825 ms 92964 KB Output is correct - L = 30
12 Correct 62 ms 92964 KB Output is correct - L = 30
13 Correct 219 ms 92964 KB Output is correct - L = 30
14 Correct 162 ms 92964 KB Output is correct - L = 30
15 Correct 62 ms 92964 KB Output is correct - L = 30
16 Correct 81 ms 92964 KB Output is correct - L = 30
17 Correct 105 ms 92964 KB Output is correct - L = 30
18 Correct 95 ms 92964 KB Output is correct - L = 30
19 Correct 66 ms 92964 KB Output is correct - L = 30
20 Correct 75 ms 92964 KB Output is correct - L = 30
21 Correct 111 ms 92964 KB Output is correct - L = 30
22 Correct 798 ms 92964 KB Output is correct - L = 30
23 Correct 762 ms 92964 KB Output is correct - L = 30
24 Correct 792 ms 92964 KB Output is correct - L = 30