oj.uz

답안 #25686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25686 2017-06-23T14:31:40 Z youngyojun 한자 끝말잇기 (JOI14_kanji) C++11
0 / 100
 289 ms 81336 KB 
#include "Annalib.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INFLL (3700000000000000099ll)
#define MAXN (305)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
static void write(int N) {
	for(int i = 0; i < 7; i++) Tap((N & (1<<i)) ? 1 : 0);
}

static vector<int> VQ[6];
static ll rd[MAXN][MAXN];
static ll d[MAXN][MAXN];

void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]) {
	for(int i = 0; i < N; i++) fill(d[i], d[i]+MAXN, INFLL);
	for(int i = 0; i < M; i++) d[A[i]][B[i]] = C[i];
	for(int i = 0; i < K; i++) d[A[U[i]]][B[U[i]]] = INFLL;
	for(int i = 0; i < N; i++) d[i][i] = 0;
	for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) upmin(d[i][j], d[i][k]+d[k][j]);
	for(int i = 0; i < N; i++) fill(rd[i], rd[i]+MAXN, INFLL);
	for(int i = 0; i < M; i++) rd[A[i]][B[i]] = C[i];
	for(int i = 0; i < N; i++) d[i][i] = 0;
	for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++)
		upmin(rd[i][j], rd[i][k] + rd[k][j]);
	for(int i = 0; i < Q; i++) {
		bool flag = false;
		for(int j = 0; j < K; j++)
			if(rd[S[i]][T[i]] == d[S[i]][A[U[j]]] + C[U[j]] + d[B[U[j]]][T[i]]) {
				flag = true; VQ[j].pb(i);
			}
		if(!flag) VQ[5].pb(i);
	}
	for(int i = 0; i <= 5; i++) write(sz(VQ[i]));
}
#include "Brunolib.h"
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INFLL (3700000000000000099ll)
#define MAXN (305)
#define MAXQ (65)
#define MAXH (537825)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
const lll INFLLL = (lll)INFLL * MAXN * MAXN;

static unordered_map<int, int> HASH[61][61]; static int HASHn = 0;
static char HA[MAXH], HB[MAXH], HC[MAXH], HD[MAXH], HE[MAXH];
static lll dp[2][MAXH];
static char rdp[62][MAXH];
static bitset<MAXH> chk[62];
static ll d[MAXN][MAXN];
static ll rawd[MAXN][MAXN];
static int rawidx[MAXN][MAXN];
static ll Y[MAXQ][5];
static int X[1005], Xn = 0, L;
static int AnsQ[MAXQ];
static int Qsz[6];

static int readBit() { return X[Xn++]; }
static int readNum() {
	int ret = 0; for(int i = 0; i < 7; i++) ret += readBit() ? (1<<i) : 0;
	return ret;
}
static void f(vector<int>& V, const int N, int S, int E) {
	if(S == E) return;
	if(d[S][E] == rawd[S][E] && -1 != rawidx[S][E]) { V.pb(rawidx[S][E]); return; }
	for(int i = 0; i < N; i++) {
		if(i == S || i == E) continue;
		if(d[S][E] == d[S][i] + d[i][E]) {
			f(V, N, S, i); f(V, N, i, E);
			return;
		}
	}
}
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[]) {
	for(int i = 0; i < N; i++) fill(d[i], d[i]+MAXN, INFLL);
	for(int i = 0; i < M; i++) if(-1 != C[i]) d[A[i]][B[i]] = C[i];
	for(int i = 0; i < N; i++) d[i][i] = 0;
	for(int k = 0; k < N; k++) for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) upmin(d[i][j], d[i][k]+d[k][j]);
	for(int i = 0; i < N; i++) fill(rawd[i], rawd[i]+MAXN, -1);
	for(int i = 0; i < M; i++) rawd[A[i]][B[i]] = C[i];
	for(int i = 0; i < N; i++) fill(rawidx[i], rawidx[i]+MAXN, -1);
	for(int i = 0; i < M; i++) rawidx[A[i]][B[i]] = i;
	L = _L; for(int i = 0; i < L; i++) X[i] = _X[i];
	for(int i = 0; i <= 5; i++) Qsz[i] = readNum();
	for(int i = 0; i < Q; i++) for(int j = 0; j < 5; j++)
		Y[i][j] = d[S[i]][T[i]] - (d[S[i]][A[U[j]]] + d[B[U[j]]][T[i]]);
	for(int a = 0; a <= Qsz[0]; a++) for(int b = 0; b <= Qsz[1]; b++) for(int c = 0; c <= Qsz[2]; c++)
		for(int d = 0; d <= Qsz[3]; d++) for(int e = 0; e <= Qsz[4]; e++) {
			HA[HASHn] = a; HB[HASHn] = b; HC[HASHn] = c; HD[HASHn] = d; HE[HASHn] = e;
			HASH[a][b][61*61*c+61*d+e] = HASHn++;
		}
	for(int i = 0; i < 2; i++) fill(dp[i], dp[i]+MAXH, -INFLLL);
	for(int i = 0; i <= Q; i++) fill(rdp[i], rdp[i]+MAXH, -1);
	chk[0][0] = true; dp[0][0] = 0;
	for(int i = 0; i < Q; i++) {
		lll bt;
		for(int j = 0; j < HASHn; j++) {
			if(!chk[j][i]) continue;
			int a = HA[j], b = HB[j], c = HC[j], d = HD[j], e = HE[j], idx;
			if(a+1 <= Qsz[0]) {
				idx = HASH[a+1][b][61*61*c+61*d+e];
				chk[idx][i+1] = true;
				bt = dp[i&1][j] + Y[i][0];
				if(dp[(i+1)&1][idx] < bt) {
					dp[(i+1)&1][idx] = bt; rdp[i+1][idx] = 0;
				}
			}
			if(b+1 <= Qsz[1]) {
				idx = HASH[a][b+1][61*61*c+61*d+e];
				chk[idx][i+1] = true;
				bt = dp[i&1][j] + Y[i][1];
				if(dp[(i+1)&1][idx] < bt) {
					dp[(i+1)&1][idx] = bt; rdp[i+1][idx] = 1;
				}
			}
			if(c+1 <= Qsz[2]) {
				idx = HASH[a][b][61*61*(c+1)+61*d+e];
				chk[idx][i+1] = true;
				bt = dp[i&1][j] + Y[i][2];
				if(dp[(i+1)&1][idx] < bt) {
					dp[(i+1)&1][idx] = bt; rdp[i+1][idx] = 2;
				}
			}
			if(d+1 <= Qsz[3]) {
				idx = HASH[a][b][61*61*c+61*(d+1)+e];
				chk[idx][i+1] = true;
				bt = dp[i&1][j] + Y[i][3];
				if(dp[(i+1)&1][idx] < bt) {
					dp[(i+1)&1][idx] = bt; rdp[i+1][idx] = 3;
				}
			}
			if(e+1 <= Qsz[4]) {
				idx = HASH[a][b][61*61*c+61*d+e+1];
				chk[idx][i+1] = true;
				bt = dp[i&1][j] + Y[i][4];
				if(dp[(i+1)&1][idx] < bt) {
					dp[(i+1)&1][idx] = bt; rdp[i+1][idx] = 4;
				}
			}
			chk[j][i+1] = true;
			if(dp[(i+1)&1][j] < dp[i&1][j]) {
				dp[(i+1)&1][j] = dp[i&1][j]; rdp[i+1][j] = 5;
			}
		}
		fill(dp[i&1], dp[i&1]+MAXH, -INFLLL);
	}
	for(int i = Q, a = Qsz[0], b = Qsz[1], c = Qsz[2], d = Qsz[3], e = Qsz[4]; i; i--) {
		AnsQ[i-1] = rdp[i][HASH[a][b][61*61*c+d*61+e]];
		if(0 == AnsQ[i-1]) a--;
		else if(1 == AnsQ[i-1]) b--;
		else if(2 == AnsQ[i-1]) c--;
		else if(3 == AnsQ[i-1]) d--;
		else if(4 == AnsQ[i-1]) e--;
	}
	for(int i = 0; i < Q; i++) {
		vector<int> V;
		if(5 == AnsQ[i]) {
			f(V, N, S[i], T[i]);
		} else {
			f(V, N, S[i], A[U[AnsQ[i]]]);
			V.pb(U[AnsQ[i]]);
			f(V, N, B[U[AnsQ[i]]], T[i]);
		}
		for(int v : V) Answer(v);
		Answer(-1);
	}
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 71332 KB Output is correct - L = 42
2 Correct 118 ms 71332 KB Output is correct - L = 42
3 Incorrect 109 ms 71332 KB Output isn't correct - Wrong Answer [9]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 164 ms 77700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 149 ms 77700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 77700 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 135 ms 77700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 164 ms 77700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 202 ms 71332 KB Output is correct - L = 42
4 Correct 161 ms 71332 KB Output is correct - L = 42
5 Runtime error 188 ms 81336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 146 ms 76188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 202 ms 71332 KB Output is correct - L = 42
8 Correct 215 ms 71332 KB Output is correct - L = 42
9 Runtime error 135 ms 77996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 156 ms 77996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 129 ms 77996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 228 ms 71332 KB Output is correct - L = 42
13 Correct 289 ms 71332 KB Output is correct - L = 42
14 Runtime error 149 ms 76188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Correct 198 ms 71332 KB Output is correct - L = 42
16 Correct 221 ms 71332 KB Output is correct - L = 42
17 Correct 175 ms 71332 KB Output is correct - L = 42
18 Runtime error 145 ms 71332 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 122 ms 71332 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 231 ms 71332 KB Output is correct - L = 42
21 Correct 216 ms 71332 KB Output is correct - L = 42
22 Runtime error 132 ms 77996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 145 ms 77996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 152 ms 77996 KB Execution killed with signal 11 (could be triggered by violating memory limits)