oj.uz

Submission #25686

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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)