#include "Annalib.h"
#include <stdio.h>
#include <string.h>
#define N 300
#define Q 60
#define K 5
void Anna(int n, int m, int a[], int b[], long long c[], int q, int s[], int t[], int k, int u[]) {
static long long dp[N][N], dp2[N][N];
unsigned long long message;
static int ii[Q], ii_[Q], brk[K], ll[K + 1], rr[K + 1], rr_[K], ban[999999];
memset(ban, 0, sizeof ban);
for (int i = 0; i < k; ++i)
ban[u[i]] = 1;
message = 0;
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < n; ++i) dp[i][i] = 0;
for (int i = 0; i < m; ++i) if (! ban[i]) dp[a[i]][b[i]] = c[i];
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (dp[i][k] + dp[k][j] < dp[i][j])
dp[i][j] = dp[i][k] + dp[k][j];
for (int i = 0; i < q; ++i) {
ii[i] = i;
}
ll[0] = 0;
rr[0] = q;
/* since we are forced to do this process forward (0-k),
* but multiplying directly to message will reverse the order of messages sent, (stack-like)
* Anna need to add breakpoints to message one by one, backward ordered */
int gap[15], at[15], sz;
sz = 0;
/*https://www.luogu.com.cn/problem/solution/AT_joisc2014_l*/
for (int p = 1; p <= k; ++p) {
if (p < k) {
for (int i_ = 0; i_ < p; ++i_) {
/* sort by f1 - f2, increasing since we want some suffix to have f1 - f2 > e2 - e1 */
for (int it = ll[i_]; it < rr[i_]; ++it)
for (int j = ll[i_] + 1; j < rr[i_]; ++j)
if (dp[b[u[i_]]][t[ii[j - 1]]] - dp[b[u[p]]][t[ii[j - 1]]] > dp[b[u[i_]]][t[ii[j]]] - dp[b[u[p]]][t[ii[j]]])
ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
/* since sorted by f1 - f2, we can find the breakpoint (suffix) of each interval */
brk[i_] = rr[i_];
for (int j = rr[i_] - 1; j >= ll[i_]; --j)
/* lhs is constant, rhs is sorted */
if (c[u[p]] - c[u[i_]] < dp[b[u[i_]]][t[ii[j]]] - dp[b[u[p]]][t[ii[j]]])
/* beneficial to switch to new group */
brk[i_] = j;
else
break;
gap[sz] = rr[i_] - ll[i_] + 1;
at[sz] = brk[i_] - ll[i_];
++sz;
}
} else { /* p == k is case where we dont use any special edges */
for (int i_ = 0; i_ < p; ++i_) {
/* sort by f1 - f2, increasing since we want some suffix to have f1 - f2 > e2 - e1 */
for (int it = ll[i_]; it < rr[i_]; ++it)
for (int j = ll[i_] + 1; j < rr[i_]; ++j)
if (dp[b[u[i_]]][t[ii[j - 1]]] + dp[s[ii[j - 1]]][a[u[i_]]] >
dp[b[u[i_]]][t[ii[j]]] + dp[s[ii[j]]][a[u[i_]]])
ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
/* since sorted by distance - edge[i_] (the latter is constant,
* we can find the breakpoint (suffix) of each interval trivially */
brk[i_] = rr[i_];
for (int j = rr[i_] - 1; j >= ll[i_]; --j)
if (dp[s[ii[j]]][t[ii[j]]] < dp[s[ii[j]]][a[u[i_]]] + c[u[i_]] + dp[b[u[i_]]][t[ii[j]]])
brk[i_] = j;
else
break;
gap[sz] = rr[i_] - ll[i_] + 1;
at[sz] = brk[i_] - ll[i_];
++sz;
}
}
/* move stuff */
int qwq = 0;
for (int i_ = 0; i_ < p; ++i_) {
ll[i_] = qwq;
for (int j = ll[i_]; j < brk[i_]; ++j)
ii_[qwq++] = ii[j];
rr_[i_] = rr[i_];
rr[i_] = qwq;
//printf(" [%d] is now [%d %d)\n",i_,ll[i_],rr[i_]);
}
ll[p] = qwq;
for (int i_ = 0; i_ < p; ++i_)
for (int j = brk[i_]; j < rr_[i_]; ++j)
ii_[qwq++] = ii[j];
rr[p] = qwq;
memcpy(ii, ii_, sizeof ii);
}
while (sz) {
--sz;
message = message * gap[sz] + at[sz];
}
for (int i = 0; i < 64; ++i)
Tap(message & 1), message >>= 1;
}
#include "Brunolib.h"
#include <stdio.h>
#include <string.h>
#define N 300
#define Q 60
#define K 5
void PATH(int bt[N][N], int id[N][N], int s, int t) {
if (s == t)
return;
if (bt[s][t] == -1) {
Answer(id[s][t]);
return;
}
PATH(bt, id, s, bt[s][t]);
PATH(bt, id, bt[s][t], t);
}
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[]) {
static long long dp[N][N]/* shortest path with backtrack */;
static int bt[N][N], id[N][N];
static int ii[Q], ii_[Q], brk[K], ll[K + 1], rr[K + 1], rr_[K];
unsigned long long message;
message = 0;
for (int i = 63; i >= 0; --i)
message = (message << 1) | x[i];
memset(bt, -1, sizeof bt);
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < n; ++i) dp[i][i] = 0;
for (int i = 0; i < m; ++i) if (~ c[i])
dp[a[i]][b[i]] = c[i], id[a[i]][b[i]] = i;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
if (dp[i][k] + dp[k][j] < dp[i][j]) {
dp[i][j] = dp[i][k] + dp[k][j];
bt[i][j] = k;
}
for (int i = 0; i < q; ++i)
ii[i] = i;
ll[0] = 0;
rr[0] = q;
/*https://www.luogu.com.cn/problem/solution/AT_joisc2014_l*/
for (int p = 1; p <= k; ++p) {
if (p == k) {
for (int i_ = 0; i_ < p; ++i_)
for (int it = ll[i_]; it < rr[i_]; ++it)
for (int j = ll[i_] + 1; j < rr[i_]; ++j)
if (dp[b[u[i_]]][t[ii[j - 1]]] + dp[s[ii[j - 1]]][a[u[i_]]] >
dp[b[u[i_]]][t[ii[j]]] + dp[s[ii[j]]][a[u[i_]]])
ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
} else {
for (int i_ = 0; i_ < p; ++i_ )
for (int it = ll[i_]; it < rr[i_]; ++it)
for (int j = ll[i_] + 1; j < rr[i_]; ++j)
if (dp[b[u[i_]]][t[ii[j - 1]]] - dp[b[u[p]]][t[ii[j - 1]]] > dp[b[u[i_]]][t[ii[j]]] - dp[b[u[p]]][t[ii[j]]])
ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
}
for (int i_ = 0; i_ < p; ++i_) {
brk[i_] = message % (rr[i_] - ll[i_] + 1);
message /= rr[i_] - ll[i_] + 1;
}
/* move stuff */
int qwq = 0;
for (int i_ = 0; i_ < p; ++i_) {
ll[i_] = qwq;
for (int j = ll[i_]; j < brk[i_]; ++j)
ii_[qwq++] = ii[j];
rr_[i_] = rr[i_];
rr[i_] = qwq;
}
ll[p + 1] = qwq;
for (int i_ = 0; i_ < p; ++i_)
for (int j = brk[i_]; j < rr_[i_]; ++j)
ii_[qwq++] = ii[j];
rr[p + 1] = qwq;
memcpy(ii, ii_, sizeof ii);
}
/* we got all needed information to answer queries, now backtracking pain */
for (int group, i = 0; i < q; ++i) {
group = -1;
for (int i_ = 0; i_ <= k; ++i_)
if (ll[i_] <= i && i < rr[i_]) {
group = i_;
break;
}
//printf(" group = %d\n", group);
if (!~group) __builtin_trap();
if (k == group) {
PATH(bt, id, s[i], t[i]);
} else {
int a_, b_;
a_ = a[u[group]], b_ = b[u[group]];
PATH(bt, id, s[i], a_);
if (a_ != b_)
Answer(id[a_][b_]);
PATH(bt, id, b_, t[i]);
}
Answer(-1);
}
}
