oj.uz

답안 #5998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5998 2014-06-12T14:04:10 Z ainta 한자 끝말잇기 (JOI14_kanji) C++
0 / 100
 312 ms 12620 KB 
#include "Annalib.h"
#define INF 4000000000000000000LL
long long w[301][301];
long long w2[301][301];
bool v[90010];

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;
	long long Mn, tp;
	for (i = 0; i < K; i++){
		v[U[i]] = true;
	}
	for (i = 0; i < N; i++){
		for (j = 0; j < N; j++){
			if (i != j)w[i][j] = w2[i][j] = INF;
			else w[i][j] = w2[i][j] = 0;
		}
	}
	for (i = 0; i < M; i++){
		w[A[i]][B[i]] = C[i];
		if (!v[i])w2[A[i]][B[i]] = C[i];
	}
	for (i = 0; i < N; i++){
		for (j = 0; j < N; j++){
			for (k = 0; k < N; k++){
				if (w[j][k]>w[j][i] + w[i][k])w[j][k] = w[j][i] + w[i][k];
				if (w2[j][k]>w2[j][i] + w2[i][k])w2[j][k] = w2[j][i] + w2[i][k];
			}
		}
	}
	for (i = 0; i < K; i++){
		Mn = INF;
		x = y = -1;
		for (j = 0; j < N; j++){
			for (k = 0; k < N; k++){
				tp = w[j][k] - w2[j][A[U[i]]] - w2[B[U[i]]][k];
				if (tp != C[U[i]])continue;
				if (Mn > w2[j][k] - w[j][k]){
					Mn = w2[j][k] - w[j][k];
					x = j, y = k;
				}
			}
		}
		if (x == -1) x = (1 << 17) - 1;
		else x = x*N + y;
		for (j = 0; j < 17; j++){
			if (x&(1 << j))Tap(1);
			else Tap(0);
		}
	}
}

#include "Brunolib.h"
#define INF 4000000000000000000LL
long long dis[301][301];
int num[301][301], n;
bool vis[90010];
void Do(int S, int T)
{
	if (S == T)return;
	int i, x, y;
	long long Mn = INF;
	for (i = 0; i < n; i++){
		if (num[S][i] != -1 && dis[S][i] + dis[i][T] == dis[S][T] && Mn > dis[S][i]){
			Mn = dis[S][i];
			x = i;
			y = num[S][i];
		}
	}
	Answer(y);
	Do(x, T);
}
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;
	for (i = 0; i < K; i++){
		vis[U[i]] = true;
	}
	for (i = 0; i < N; i++){
		for (j = 0; j < N; j++){
			num[i][j] = -1;
			if (i != j){
				dis[i][j] = INF;
			}
			else dis[i][j] = 0;
		}
	}
	for (i = 0; i < M; i++){
		num[A[i]][B[i]] = i;
		if (!vis[i]){
			dis[A[i]][B[i]] = C[i];
		}
	}
	for (i = 0; i < N; i++){
		for (j = 0; j < N; j++){
			for (k = 0; k < N; k++){
				if (dis[j][k]>dis[j][i] + dis[i][k])dis[j][k] = dis[j][i] + dis[i][k];
			}
		}
	}
	for (i = 0; i < K; i++){
		x = 0;
		for (j = 0; j < 17; j++){
			if (X[i * 17 + j])x += (1 << j);
		}
		if (x == (1 << 17) - 1)continue;
		y = x%N; x /= N;
		dis[A[U[i]]][B[U[i]]] = dis[x][y] - dis[x][A[U[i]]] - dis[B[U[i]]][y] - 1;
	}
	for (i = 0; i < N; i++){
		for (j = 0; j < N; j++){
			for (k = 0; k < N; k++){
				if (dis[j][k]>dis[j][i] + dis[i][k])dis[j][k] = dis[j][i] + dis[i][k];
			}
		}
	}
	for (i = 0; i < Q; i++){
		Do(S[i], T[i]);
		Answer(-1);
	}
}

Compilation message

Bruno.cpp: In function 'void Do(int, int)':
Bruno.cpp:18:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
  Answer(y);
           ^
Bruno.cpp:8:2: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (S == T)return;
  ^

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 122 ms 12620 KB Output is correct - L = 85
2 Correct 119 ms 12620 KB Output is correct - L = 85
3 Correct 109 ms 12620 KB Output is correct - L = 85
4 Correct 119 ms 12620 KB Output is correct - L = 85
5 Correct 114 ms 12620 KB Output is correct - L = 85
6 Correct 112 ms 12620 KB Output is correct - L = 85
7 Incorrect 105 ms 12620 KB Output isn't correct - Wrong Answer [9]
8 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 12620 KB Output is correct - L = 85
2 Incorrect 129 ms 12620 KB Output isn't correct - Wrong Answer [9]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 108 ms 12620 KB Output is correct - L = 85
2 Incorrect 111 ms 12620 KB Output isn't correct - Wrong Answer [9]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 12620 KB Output is correct - L = 85
2 Incorrect 115 ms 12620 KB Output isn't correct - Wrong Answer [9]
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 114 ms 12620 KB Output is partially correct - L = 85
2 Incorrect 109 ms 12620 KB Output isn't correct - Wrong Answer [9]
3 Partially correct 119 ms 12620 KB Output is partially correct - L = 85
4 Partially correct 122 ms 12620 KB Output is partially correct - L = 85
5 Partially correct 122 ms 12620 KB Output is partially correct - L = 85
6 Partially correct 122 ms 12620 KB Output is partially correct - L = 85
7 Partially correct 122 ms 12620 KB Output is partially correct - L = 85
8 Partially correct 114 ms 12620 KB Output is partially correct - L = 85
9 Incorrect 115 ms 12620 KB Output isn't correct - Wrong Answer [9]
10 Incorrect 112 ms 12620 KB Output isn't correct - Wrong Answer [9]
11 Incorrect 108 ms 12620 KB Output isn't correct - Wrong Answer [9]
12 Partially correct 122 ms 12620 KB Output is partially correct - L = 85
13 Partially correct 312 ms 12620 KB Output is partially correct - L = 85
14 Partially correct 135 ms 12620 KB Output is partially correct - L = 85
15 Partially correct 139 ms 12620 KB Output is partially correct - L = 85
16 Partially correct 138 ms 12620 KB Output is partially correct - L = 85
17 Incorrect 139 ms 12620 KB Output isn't correct - Wrong Answer [9]
18 Partially correct 155 ms 12620 KB Output is partially correct - L = 85
19 Incorrect 114 ms 12620 KB Output isn't correct - Wrong Answer [9]
20 Partially correct 142 ms 12620 KB Output is partially correct - L = 85
21 Partially correct 159 ms 12620 KB Output is partially correct - L = 85
22 Incorrect 108 ms 12620 KB Output isn't correct - Wrong Answer [9]
23 Incorrect 114 ms 12620 KB Output isn't correct - Wrong Answer [9]
24 Incorrect 108 ms 12620 KB Output isn't correct - Wrong Answer [9]