Submission #25686

#	Time	Username	Problem	Language	Result	Execution time	Memory
25686		youngyojun	한자 끝말잇기 (JOI14_kanji)	C++11	0 / 100	289 ms	81336 KiB

Anna

#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]));
}

Bruno

#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
• Subtask 2: 0 / 22
• Subtask 3: 0 / 8
• Subtask 4: 0 / 40
• Subtask 5: 0 / 20