#include "Aoi.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
typedef long long ll;
const ll INF = 1e18;
int n;
vector<int> A, B;
vector<ll> C, realC;
vector<int> con[10005];
ll dist[10005], real_dist[10005];
int prec[10005];
void calc_dist_src(int src)
{
for(int i=0;i<n;i++)
{
dist[i] = INF;
real_dist[i] = 0;
prec[i] = -1;
}
priority_queue<pair<ll,int>> pq;
dist[src] = 0;
pq.push({0, src});
while(!pq.empty())
{
int nod = pq.top().second;
ll cdist = -pq.top().first;
pq.pop();
if(cdist != dist[nod])
continue;
for(auto eid:con[nod])
{
int adj = A[eid] + B[eid] - nod;
ll w = C[eid];
if(dist[adj] > dist[nod] + w)
{
dist[adj] = dist[nod] + w;
prec[adj] = eid;
real_dist[adj] = real_dist[nod] + realC[eid];
pq.push({-dist[adj], adj});
}
}
}
}
}
std::string aoi(int N, int M, int Q, int K, std::vector<int> copA,
std::vector<int> copB, std::vector<ll> copC,
std::vector<int> T, std::vector<int> X)
{
mt19937 rnd(139881);
const int CT = 500;
assert(n == 0);
n = N;
A = copA;
B = copB;
C = copC;
realC = copC;
for(int i=0;i<M;i++)
{
con[A[i]].push_back(i);
con[B[i]].push_back(i);
}
calc_dist_src(0);
vector<ll> init_dist(Q);
vector<vector<int>> important(Q);
for(int i=0;i<Q;i++)
{
init_dist[i] = dist[T[i]];
vector<bool> used(M,0);
int cur = T[i];
while(cur != 0)
{
int eid = prec[cur];
cur = A[eid] + B[eid] - cur;
used[eid] = 1;
}
for(int j=0;j<K;j++)
if(used[X[j]])
important[i].push_back(j);
}
vector<int> good_masks;
for(int i=0;i<Q;i++)
good_masks.push_back(1<<i);
/*vector<vector<ll>> myd(Q, vector<ll>(N,0));
for(int i=0;i<Q;i++)
{
for(int j=0;j<K;j++)
C[X[j]] = INF;
for(int j:important[i])
C[X[j]] = 1;
calc_dist_src(T[i]);
for(int u=0;u<N;u++)
myd[i][u] = dist[u];
}
vector<vector<bool>> can_be_together(Q,vector<bool>(Q, 1));
for(int i=0;i<Q;i++)
{
for(int j=0;j<Q;j++)
{
if(i == j)
continue;
for(int eid:important[j])
{
for(auto [u,v] : vector<pair<int,int>>{{A[X[eid]], B[X[eid]]}, {B[X[eid]], A[X[eid]]}})
{
if(myd[i][v] + )
}
}
}
}*/
vector<int> ord;
for(int mask=1;mask<(1<<Q);mask++)
if(__builtin_popcount(mask) > 1)
ord.push_back(mask);
shuffle(ord.begin(), ord.end(), rnd);
for(int pas=0;pas<min(CT, (int)ord.size());pas++)
{
int mask = ord[pas];
for(int i=0;i<K;i++)
C[X[i]] = INF;
for(int i=0;i<Q;i++)
if((1<<i)&mask)
for(int j:important[i])
C[X[j]] = 1;
calc_dist_src(0);
bool bun = 1;
for(int i=0;i<Q;i++)
{
if(realC[T[i]] != init_dist[i])
{
bun = 0;
break;
}
}
if(bun)
good_masks.push_back(mask);
}
vector<bool> isgood((1<<Q), 0);
for(int x:good_masks)
isgood[x] = 1;
vector<int> dp((1<<Q), Q + 5);
vector<int> ult((1<<Q), -1);
dp[0] = 0;
/*for(int mask=1;mask<(1<<Q);mask++)
{
vector<int> submasks;
int cur = mask;
while(cur != 0)
{
cur = (cur - 1) & mask;
submasks.push_back(cur);
}
for(int subm:submasks)
{
assert((mask | subm) == mask);
if(isgood[mask - subm] && dp[mask] > dp[subm] + 1)
{
dp[mask] = dp[subm] + 1;
ult[mask] = mask - subm;
}
}
}*/
for(int mask=1;mask<(1<<Q);mask++)
{
for(int good:good_masks)
{
if((mask | good) == mask && dp[mask] > dp[mask - good] + 1)
{
dp[mask] = dp[mask - good] + 1;
ult[mask] = good;
}
}
}
assert(dp[(1<<Q) - 1] != Q + 5);
string sol;
int mask = (1<<Q) - 1;
while(mask > 0)
{
int now = ult[mask];
mask -= now;
vector<bool> used(M,0);
for(int i=0;i<Q;i++)
{
if((1<<i)&now)
{
for(int j:important[i])
used[X[j]] = 1;
}
}
for(int i=0;i<Q;i++)
{
if((1<<i)&now)
sol.push_back('1');
else
sol.push_back('0');
}
for(int i=0;i<K;i++)
{
if(used[X[i]])
sol.push_back('1');
else
sol.push_back('0');
}
}
return sol;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
using namespace std;
namespace
{
typedef long long ll;
const ll INF = 1e18;
int n;
vector<int> A, B;
vector<ll> C;
vector<int> con[10005];
ll dist[10005];
int prec[10005];
void calc_dist()
{
for(int i=0;i<n;i++)
{
dist[i] = INF;
prec[i] = -1;
}
priority_queue<pair<ll,int>> pq;
dist[0] = 0;
pq.push({0, 0});
while(!pq.empty())
{
int nod = pq.top().second;
ll cdist = -pq.top().first;
pq.pop();
if(cdist != dist[nod])
continue;
for(auto eid:con[nod])
{
int adj = A[eid] + B[eid] - nod;
ll w = C[eid];
if(dist[adj] > dist[nod] + w)
{
dist[adj] = dist[nod] + w;
prec[adj] = eid;
pq.push({-dist[adj], adj});
}
}
}
}
}
void bitaro(int N, int M, int Q, int K, std::vector<int> copA, std::vector<int> copB,
std::vector<long long> copC, std::vector<int> T, std::vector<int> X,
std::string s)
{
n = N;
A = copA;
B = copB;
C = copC;
for(int i=0;i<M;i++)
{
con[A[i]].push_back(i);
con[B[i]].push_back(i);
}
vector<vector<int>> ans(Q);
assert((int)s.size() % (Q+K) == 0);
for(int le=0;le<s.size();le+=Q+K)
{
for(int i=0;i<K;i++)
{
if(s[le + Q + i] == '1')
{
C[X[i]] = 1;
}
else
{
C[X[i]] = INF;
}
}
calc_dist();
for(int i=0;i<Q;i++)
{
if(s[le + i] == '1')
{
int cur = T[i];
while(cur != 0)
{
int eid = prec[cur];
ans[i].push_back(eid);
cur = A[eid] + B[eid] - cur;
}
reverse(ans[i].begin(), ans[i].end());
}
}
}
for(int i=0;i<Q;i++)
answer(ans[i]);
}
/*
3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1
*/
