| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 25628 |
2017-06-23T08:49:19 Z |
윤교준(#1076) |
한자 끝말잇기 (JOI14_kanji) |
C++11 |
|
225 ms |
17144 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 clv(V) (V).clear()
#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 MAXM (90005)
#define MAXQ (65)
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 int uptwo[MAXQ+1];
static inline void writeNum(int N, int Cnt, int MAXNUM = -1) {
if(MAXNUM == (1 << (Cnt-1)) && N == MAXNUM) { Tap(1); return; }
for(int i = Cnt-1; ~i; i--) Tap((N & (1<<i)) ? 1 : 0);
//printf("WRITENUM %d %d\n", N, Cnt);
}
static int A[MAXM], B[MAXM];
static ll C[MAXM];
static int S[MAXQ], T[MAXQ];
static int U[5];
static int N, M, Q, K;
static ll d[MAXN][MAXN];
static ll getDist(int S, int E, int QN) {
if(5 == QN) return d[S][E];
ll ret = d[S][A[U[QN]]] + C[U[QN]] + d[B[U[QN]]][E];
return INFLL <= ret ? INFLL : ret;
}
static void querycountF(const vector<int>& VQ, vector<int>& VQA, vector<int>& VQB, int QA, int QB) {
clv(VQA); clv(VQB); for(int v : VQ) {
const ll la = getDist(S[v], T[v], QA);
const ll lb = getDist(S[v], T[v], QB);
if(la == INFLL) {
VQB.pb(v);
} else if(la < lb) {
VQA.pb(v);
} else {
VQB.pb(v);
}
}
}
static void process() {
vector<int> VQ[6]; for(int i = 0; i < Q; i++) VQ[0].pb(i);
vector<int> VA, VB; // j, i
for(int i = 1; i <= 5; i++) {
for(int j = 0; j < i; j++) {
if((i < 5 && K <= i) || (j < 5 && K <= j)) continue;
querycountF(VQ[j], VA, VB, j, i);
//printf("TRY TO WRITE %d %d : %d %d\n", j, i, sz(VQ[j]), uptwo[sz(VQ[j])]);
if(sz(VA) < sz(VB)) { Tap(1); writeNum(sz(VA), max(1, uptwo[sz(VQ[j])]-1)); }
else { Tap(0); writeNum(sz(VB), max(1, uptwo[sz(VQ[j])]-1)); }
//writeNum(sz(VA), uptwo[sz(VQ[j])], sz(VQ[j]));
clv(VQ[j]); VQ[j] = VA; for(int v : VB) VQ[i].pb(v);
}
}
/*for(int i = 0; i <= 5; i++) {
printf("QUERIES %d\n", i);
for(int v : VQ[i]) printf("%d ", v); puts("");
}*/
}
void Anna(int _N, int _M, int _A[], int _B[], long long _C[], int _Q, int _S[], int _T[], int _K, int _U[]) {
uptwo[0] = 1; for(int i = 1; i <= MAXQ; i++) uptwo[i] = uptwo[i/2]+1;
for(int i = 1; i <= MAXQ; i++) uptwo[i]--;
N = _N; M = _M; Q = _Q; K = _K;
for(int i = 0; i < M; i++) { A[i] = _A[i]; B[i] = _B[i]; C[i] = _C[i]; }
for(int i = 0; i < Q; i++) { S[i] = _S[i]; T[i] = _T[i]; }
for(int i = 0; i < K; i++) U[i] = _U[i];
for(int i = 0; i < N; i++) fill(d[i], d[i]+MAXN, INFLL);
for(int i = 0; i < N; i++) d[i][i] = 0;
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 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]);
process();
}
#include "Brunolib.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 clv(V) (V).clear()
#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 MAXM (90005)
#define MAXQ (65)
#define MAXL (1005)
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 int uptwo[MAXQ+1];
static int A[MAXM], B[MAXM];
static ll C[MAXM];
static int S[MAXQ], T[MAXQ];
static int U[5];
static int X[MAXL]; static int Xn = 0;
static int N, M, Q, K, L;
static vector<int> AnsPath[MAXQ];
static vector<int> VQ[6];
static ll d[MAXN][MAXN];
static ll rawd[MAXN][MAXN];
static int rawidx[MAXN][MAXN];
static inline ll bojeong(const ll n) { return INFLL <= n ? INFLL : n; }
static inline int readBit() { return X[Xn++]; }
static inline int readNum(int Cnt, int MAXNUM = -1) {
if((1 << (Cnt-1)) == MAXNUM) { if(readBit()) { return MAXNUM; } else Xn--; }
int ret = 0;
for(int i = Cnt-1; ~i; i--) ret += readBit() ? (1<<i) : 0;
//printf("READNUM %d %d\n", ret, Cnt);
return ret;
}
static void splitqueryF(const vector<int>& VQ, vector<int>& VA, vector<int>& VB, const int QA, const int QB, const int cnt) {
clv(VA); clv(VB);
if(5 == QB) {
vector<pli> V;
for(int v : VQ) {
bool flag1 = false, flag2 = false;
if(d[S[v]][A[U[QA]]] == INFLL || d[B[U[QA]]][T[v]] == INFLL) flag1 = true;
if(d[S[v]][T[v]] == INFLL) flag2 = true;
if(flag1) { V.pb({INFLL, v}); }
else if(flag2) { V.pb({-INFLL, v}); }
else V.pb({d[S[v]][A[U[QA]]] + d[B[U[QA]]][T[v]] - d[S[v]][T[v]], v});
}
sorv(V);
for(int i = 0; i < cnt; i++) VA.pb(V[i].second);
for(int i = cnt; i < sz(V); i++) VB.pb(V[i].second);
} else {
vector<pli> V;
for(int v : VQ) {
bool flag1 = false, flag2 = false;
if(d[S[v]][A[U[QA]]] == INFLL || d[B[U[QA]]][T[v]] == INFLL) flag1 = true;
if(d[S[v]][A[U[QB]]] == INFLL || d[B[U[QB]]][T[v]] == INFLL) flag2 = true;
if(flag1) { V.pb({INFLL, v}); }
else if(flag2) { V.pb({-INFLL, v}); }
else V.pb({d[B[U[QA]]][T[v]] - d[B[U[QB]]][T[v]], v});
}
sorv(V);
for(int i = 0; i < cnt; i++) VA.pb(V[i].second);
for(int i = cnt; i < sz(V); i++) VB.pb(V[i].second);
}
}
static void process() {
for(int i = 0; i < Q; i++) VQ[0].pb(i);
vector<int> VA, VB; // j, i
for(int i = 1; i <= 5; i++) {
for(int j = 0; j < i; j++) { // j, i
if((i < 5 && K <= i) || (j < 5 && K <= j)) continue;
const int ang = readBit();
const int tmpret = readNum(max(1, uptwo[sz(VQ[j])]-1), sz(VQ[j]));
const int ret = ang ? tmpret : sz(VQ[j]) - tmpret;
splitqueryF(VQ[j], VA, VB, j, i, ret);
clv(VQ[j]); VQ[j] = VA; for(int v : VB) VQ[i].pb(v);
}
}
}
static void getPath(vector<int>& V, 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]) {
getPath(V, S, i); getPath(V, i, E);
return;
}
}
//printf("GETPATH FUCKED %d %d\n", S, E);
}
static void getAns() {
for(int i = 0; i <= 5; i++) {
for(int v : VQ[i]) {
vector<int> &V = AnsPath[v];
//printf("GETANS %d : %d\n", v, i);
if(5 == i) {
getPath(V, S[v], T[v]);
} else {
getPath(V, S[v], A[U[i]]);
V.pb(U[i]);
getPath(V, B[U[i]], T[v]);
}
}
}
}
static void printAns() {
for(int i = 0; i < Q; i++) {
for(int v : AnsPath[i]) Answer(v);
Answer(-1);
}
}
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[]) {
uptwo[0] = 1; for(int i = 1; i <= MAXQ; i++) uptwo[i] = uptwo[i/2]+1;
for(int i = 1; i <= MAXQ; i++) uptwo[i]--;
N = _N; M = _M; Q = _Q; K = _K; L = _L;
for(int i = 0; i < M; i++) { A[i] = _A[i]; B[i] = _B[i]; C[i] = _C[i]; }
for(int i = 0; i < Q; i++) { S[i] = _S[i]; T[i] = _T[i]; }
for(int i = 0; i < K; i++) U[i] = _U[i];
for(int i = 0; i < L; i++) X[i] = _X[i];
for(int i = 0; i < N; i++) fill(rawd[i], rawd[i]+MAXN, INFLL);
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;
for(int i = 0; i < N; i++) fill(d[i], d[i]+MAXN, INFLL);
for(int i = 0; i < N; i++) d[i][i] = 0;
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 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 < L; i++) printf("%d", X[i]); puts("");
process(); getAns(); printAns();
/*for(int i = 0; i < Q; i++) {
printf("PATH %d\n", i);
for(int v : AnsPath[i]) printf("%d ", v); puts("");
}
for(int i = 0; i <= 5; i++) {
printf("QUERIES %d\n", i);
for(int v : VQ[i]) printf("%d ", v); puts("");
}*/
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 38 |
| 2 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 40 |
| 3 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 40 |
| 4 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 38 |
| 5 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 37 |
| 6 |
Correct |
76 ms |
17144 KB |
Output is correct - L = 38 |
| 7 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 36 |
| 8 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 40 |
| 9 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 40 |
| 10 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 40 |
| 11 |
Correct |
66 ms |
17144 KB |
Output is correct - L = 30 |
| 12 |
Correct |
208 ms |
17144 KB |
Output is correct - L = 40 |
| 13 |
Correct |
76 ms |
17144 KB |
Output is correct - L = 37 |
| 14 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 2 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 67 |
| 2 |
Correct |
92 ms |
17144 KB |
Output is correct - L = 68 |
| 3 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 61 |
| 4 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 61 |
| 5 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 66 |
| 6 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 65 |
| 7 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 56 |
| 8 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 66 |
| 9 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 68 |
| 10 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 69 |
| 11 |
Correct |
96 ms |
17144 KB |
Output is correct - L = 68 |
| 12 |
Correct |
62 ms |
17144 KB |
Output is correct - L = 50 |
| 13 |
Correct |
206 ms |
17144 KB |
Output is correct - L = 51 |
| 14 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 66 |
| 15 |
Correct |
99 ms |
17144 KB |
Output is correct - L = 60 |
| 16 |
Correct |
95 ms |
17144 KB |
Output is correct - L = 53 |
| 17 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 54 |
| 18 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 62 |
| 19 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 56 |
| 20 |
Correct |
92 ms |
17144 KB |
Output is correct - L = 62 |
| 21 |
Correct |
88 ms |
17144 KB |
Output is correct - L = 50 |
| 22 |
Correct |
96 ms |
17144 KB |
Output is correct - L = 69 |
| 23 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 67 |
| 24 |
Correct |
89 ms |
17144 KB |
Output is correct - L = 69 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 67 |
| 2 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 68 |
| 3 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 61 |
| 4 |
Correct |
89 ms |
17144 KB |
Output is correct - L = 61 |
| 5 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 66 |
| 6 |
Correct |
92 ms |
17144 KB |
Output is correct - L = 65 |
| 7 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 56 |
| 8 |
Correct |
88 ms |
17144 KB |
Output is correct - L = 66 |
| 9 |
Correct |
76 ms |
17144 KB |
Output is correct - L = 68 |
| 10 |
Correct |
98 ms |
17144 KB |
Output is correct - L = 69 |
| 11 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 68 |
| 12 |
Correct |
82 ms |
17144 KB |
Output is correct - L = 50 |
| 13 |
Correct |
225 ms |
17144 KB |
Output is correct - L = 51 |
| 14 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 66 |
| 15 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 60 |
| 16 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 53 |
| 17 |
Correct |
92 ms |
17144 KB |
Output is correct - L = 54 |
| 18 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 62 |
| 19 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 56 |
| 20 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 62 |
| 21 |
Correct |
89 ms |
17144 KB |
Output is correct - L = 50 |
| 22 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 69 |
| 23 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 67 |
| 24 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 69 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 67 |
| 2 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 68 |
| 3 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 61 |
| 4 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 61 |
| 5 |
Correct |
89 ms |
17144 KB |
Output is correct - L = 66 |
| 6 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 65 |
| 7 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 56 |
| 8 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 66 |
| 9 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 68 |
| 10 |
Correct |
89 ms |
17144 KB |
Output is correct - L = 69 |
| 11 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 68 |
| 12 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 50 |
| 13 |
Correct |
222 ms |
17144 KB |
Output is correct - L = 51 |
| 14 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 66 |
| 15 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 60 |
| 16 |
Correct |
82 ms |
17144 KB |
Output is correct - L = 53 |
| 17 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 54 |
| 18 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 62 |
| 19 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 56 |
| 20 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 62 |
| 21 |
Correct |
81 ms |
17144 KB |
Output is correct - L = 50 |
| 22 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 69 |
| 23 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 67 |
| 24 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 69 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
66 ms |
17144 KB |
Output is partially correct - L = 67 |
| 2 |
Partially correct |
75 ms |
17144 KB |
Output is partially correct - L = 68 |
| 3 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 61 |
| 4 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 61 |
| 5 |
Partially correct |
72 ms |
17144 KB |
Output is partially correct - L = 66 |
| 6 |
Partially correct |
72 ms |
17144 KB |
Output is partially correct - L = 65 |
| 7 |
Correct |
69 ms |
17144 KB |
Output is correct - L = 56 |
| 8 |
Partially correct |
75 ms |
17144 KB |
Output is partially correct - L = 66 |
| 9 |
Partially correct |
69 ms |
17144 KB |
Output is partially correct - L = 68 |
| 10 |
Partially correct |
69 ms |
17144 KB |
Output is partially correct - L = 69 |
| 11 |
Partially correct |
66 ms |
17144 KB |
Output is partially correct - L = 68 |
| 12 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 50 |
| 13 |
Correct |
206 ms |
17144 KB |
Output is correct - L = 51 |
| 14 |
Partially correct |
62 ms |
17144 KB |
Output is partially correct - L = 66 |
| 15 |
Correct |
75 ms |
17144 KB |
Output is correct - L = 60 |
| 16 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 53 |
| 17 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 54 |
| 18 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 62 |
| 19 |
Correct |
72 ms |
17144 KB |
Output is correct - L = 56 |
| 20 |
Correct |
84 ms |
17144 KB |
Output is correct - L = 62 |
| 21 |
Correct |
78 ms |
17144 KB |
Output is correct - L = 50 |
| 22 |
Partially correct |
96 ms |
17144 KB |
Output is partially correct - L = 69 |
| 23 |
Partially correct |
66 ms |
17144 KB |
Output is partially correct - L = 67 |
| 24 |
Partially correct |
72 ms |
17144 KB |
Output is partially correct - L = 69 |
