oj.uz

Submission #6151

# Submission time Handle Problem Language Result Execution time Memory
6151 2014-06-20T16:30:36 Z ainta 한자 끝말잇기 (JOI14_kanji) C++
0 / 100
 322 ms 20172 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[321293], par2[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;
	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 = G[K] - 1; j >= 0; j--){
			if (j && !D[j])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[i]][0] == t1&&D[j + G[i]][1] < t2)){
					D[j + G[k]][0] = t1;
					D[j + G[k]][1] = t2;
					par[j + G[k]] = i;
					par2[j + G[k]] = k;
				}
			}
		}
	}
	x = G[k] - 1;
	for (i = 0; i < Q; i++)Res[i] = -1;
	while (x){
		Res[par[x]] = par2[x];
		x -= G[par2[x]];
	}
	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);
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 20172 KB Output isn't correct - Wrong Answer [9]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 128 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 66 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 62 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 169 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 126 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 72 ms 20172 KB Output is correct - L = 30
8 Correct 66 ms 20172 KB Output is correct - L = 30
9 Runtime error 305 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 322 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 321 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 78 ms 20172 KB Output is correct - L = 30
13 Correct 232 ms 20172 KB Output is correct - L = 30
14 Runtime error 114 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 66 ms 20172 KB Output isn't correct - Wrong Answer [4]
16 Runtime error 78 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 84 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 92 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 55 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 72 ms 20172 KB Output is correct - L = 30
21 Correct 95 ms 20172 KB Output is correct - L = 30
22 Runtime error 302 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 309 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 318 ms 20172 KB Execution killed with signal 11 (could be triggered by violating memory limits)