#include "Aoi.h"
#include <bits/stdc++.h>
/*
Send the "shortest path tree of targets" along with which edges are used
*/
namespace {
std::vector<int> parents,parentedges;
std::vector<std::vector<int>> children;
std::vector<std::vector<std::pair<int,int>>> edges;
std::vector<int> targets;
std::vector<int> missinginds;
std::vector<int> reaches;
std::vector<int> ereaches;
int dfs(int cur){
int dpset=0;
for(int i=0;i<targets.size();i++){
if(targets[i]==cur){
dpset|=(1<<i);
reaches.push_back(dpset);
}
}
for(int i:children[cur]){
int oset=dfs(i);
if(oset!=0&&dpset!=0){
reaches.push_back(oset|dpset);
}
dpset|=oset;
}
if(cur){
int eind=missinginds[parentedges[cur]];
if(eind>=0){
ereaches[eind]=dpset;
}
}
return dpset;
}
}
std::string aoi(int N, int M, int Q, int K, std::vector<int> A,
std::vector<int> B, std::vector<long long> C,
std::vector<int> T, std::vector<int> X) {
targets=T;
missinginds.resize(M,-1);
for(int i=0;i<K;i++)missinginds[X[i]]=i;
parents.resize(N);
parentedges.resize(N);
children.resize(N);
edges.resize(N);
ereaches.resize(M);
for(int i=0;i<M;i++){
edges[A[i]].push_back({B[i],i});
edges[B[i]].push_back({A[i],i});
}
std::vector<long long> dists(N,1e18);
std::priority_queue<std::pair<long long,std::pair<int,int>>> dijkstra;
dijkstra.push({0,{-1,0}});//(-dist, (edgenum,index))
while(!dijkstra.empty()){
std::pair<long long,std::pair<int,int>> cur=dijkstra.top();
dijkstra.pop();
cur.first=-cur.first;
int edgenum=cur.second.first;
int curnode=cur.second.second;
if(dists[curnode]<=cur.first)continue;
dists[curnode]=cur.first;
if(curnode){
parents[curnode]=A[edgenum]^B[edgenum]^curnode;
parentedges[curnode]=edgenum;
children[parents[curnode]].push_back(curnode);
}
for(std::pair<int,int> i:edges[curnode]){
dijkstra.push({-(cur.first+C[i.second]),{i.second,i.first}});
}
}
dfs(0);
std::string s(1600, '0');
std::vector<int> stk;
std::vector<int> nreaches;
int ind=0;
for(int i:reaches){
if(i==0)continue;
if(i==(i&-i)){
stk.push_back(i);
nreaches.push_back(i);
s[ind++]='0';
for(int j=0;j<4;j++){
int cbit=__builtin_ctz(i);
s[ind++]=((cbit>>j)&1)|'0';
}
}else{
while(stk.back()!=i){
int last=stk.back();
stk.pop_back();
stk.back()|=last;
nreaches.push_back(stk.back());
s[ind++]='1';
}
}
}
for(int i=0;i<K;i++){
int creach=31;
for(int j=0;j<nreaches.size();j++){
if(ereaches[i]==nreaches[j]){
creach=j;
break;
}
}
for(int j=0;j<5;j++){
s[ind++]=((creach>>j)&1)|'0';
}
}
return s;
}
#include "Bitaro.h"
#include <bits/stdc++.h>
namespace {
} // namespace
void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B,
std::vector<long long> C, std::vector<int> T, std::vector<int> X,
std::string s) {
std::vector<std::vector<std::pair<int,int>>> edges(N);
std::vector<int> stk,rch,missinginds(M);
std::vector<int> mreach(M,2*Q-2);
for(int i=0;i<K;i++){
missinginds[X[i]]=i;
}
int ind=0;
for(int i=0;i<Q*2-1;i++){
if(s[ind++]=='0'){
int num=0;
for(int j=0;j<4;j++){
num+=(1<<j)*(s[ind++]=='1');
}
stk.push_back(1<<num);
rch.push_back(stk.back());
}else{
int comb=stk.back()+stk[stk.size()-2];
stk.pop_back();stk.back()=comb;
rch.push_back(comb);
}
}
rch.resize(32);
for(int i=0;i<K;i++){
int num=0;
for(int j=0;j<5;j++){
num+=(1<<j)*(s[ind++]=='1');
}
mreach[X[i]]=num;
}
for(int i=0;i<M;i++){
edges[A[i]].push_back({B[i],i});
edges[B[i]].push_back({A[i],i});
}
for(int qn=0;qn<Q;qn++){
std::vector<long long> dists(N,1e18);
std::priority_queue<std::pair<long long,std::pair<int,int>>> dijkstra;
std::vector<int> parents(N),parentedges(N);
dijkstra.push({0,{-1,0}});//(-dist, (edgenum,index))
while(!dijkstra.empty()){
std::pair<long long,std::pair<int,int>> cur=dijkstra.top();
dijkstra.pop();
cur.first=-cur.first;
int edgenum=cur.second.first;
int curnode=cur.second.second;
if(dists[curnode]<=cur.first)continue;
dists[curnode]=cur.first;
if(curnode){
parents[curnode]=A[edgenum]^B[edgenum]^curnode;
parentedges[curnode]=edgenum;
}
for(std::pair<int,int> i:edges[curnode]){
if(missinginds[i.second]>=0){
if(((rch[mreach[i.second]]>>qn)&1)==0)continue;
}
dijkstra.push({-(cur.first+std::max(0ll,C[i.second])),{i.second,i.first}});
}
}
std::vector<int> result;
int loc=T[qn];
while(loc!=0){
result.push_back(parentedges[loc]);
loc=parents[loc];
}
std::reverse(result.begin(),result.end());
answer(result);
}
}
