oj.uz

답안 #25676

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25676 2017-06-23T14:24:20 Z youngyojun 한자 끝말잇기 (JOI14_kanji) C++11
0 / 100
 146 ms 9196 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[62][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 <= Q; i++) fill(dp[i], dp[i]+537824+5, -INFLLL);
	for(int i = 0; i <= Q; i++) fill(rdp[i], rdp[i]+537824+5, -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][j] + Y[i][0];
				if(dp[i+1][idx] < bt) {
					dp[i+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][j] + Y[i][1];
				if(dp[i+1][idx] < bt) {
					dp[i+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][j] + Y[i][2];
				if(dp[i+1][idx] < bt) {
					dp[i+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][j] + Y[i][3];
				if(dp[i+1][idx] < bt) {
					dp[i+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][j] + Y[i][4];
				if(dp[i+1][idx] < bt) {
					dp[i+1][idx] = bt; rdp[i+1][idx] = 4;
				}
			}
			chk[j][i+1] = true;
			if(dp[i+1][j] < dp[i][j]) {
				dp[i+1][j] = dp[i][j]; rdp[i+1][j] = 5;
			}
		}
	}
	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 Runtime error 76 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 73 ms 9196 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 69 ms 9196 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 69 ms 9196 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 63 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 73 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 73 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 76 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 66 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 73 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 66 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 66 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 66 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 63 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 63 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 66 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 146 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 66 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 63 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 76 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 79 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 86 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 79 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 76 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 83 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 73 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 73 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 79 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)