#include "Aoi.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
namespace {
vector<vector<pair<pair<int, ll>, int>>> graph;
int n, m, q, k;
}
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) {
n = N, m = M, q = Q, k = K;
graph.resize(n);
for(int i = 0; i < m; i++){
graph[A[i]].emplace_back(make_pair(B[i], C[i]), i);
graph[B[i]].emplace_back(make_pair(A[i], C[i]), i);
}
priority_queue<pair<ll, pair<int, int>>, vector<pair<ll, pair<int, int>>>, greater<pair<ll, pair<int, int>>>> pq;
vector<ll> dist(n, 1e18);
dist[0] = 0;
vector<pair<int, int>> par(n);
pq.emplace(0, make_pair(0, 0));
while(!pq.empty()){
auto [d, tmp] = pq.top();
auto [node, eid] = tmp;
pq.pop();
if(dist[node] < d) continue;
if(node != 0){
par[node] = make_pair((A[eid] == node ? B[eid] : A[eid]), eid);
}
for(auto &[x, eid]: graph[node]){
if(dist[x.first] > d + x.second){
dist[x.first] = d + x.second;
pq.emplace(dist[x.first], make_pair(x.first, eid));
}
}
}
vector<bool> isq(n), isk(m);
for(auto x: T) isq[x] = 1;
for(auto x: X) isk[x] = 1;
vector<int> qtag(n, -1), ktag(m, -1);
int now;
for(int i = q - 1; i >= 0; i--){
now = T[i];
while(now != 0){
auto &[p, eid] = par[now];
if(isk[eid]) ktag[eid] = i;
now = p;
}
}
for(int i = 0; i < q; i++){
now = T[i];
while(now != 0){
auto &[p, eid] = par[now];
if(isk[eid]){
if(ktag[eid] < i){
qtag[i] = eid;
break;
}
}
now = p;
}
}
vector<int> kpos(m);
for(int i = 0; i < k; i++) kpos[X[i]] = i;
string ans;
for(int s = 0; s < k; s += 6){
int e = min(s + 5, k - 1);
ll enc = 0, base = 1;
for(int i = s; i <= e; i++){
enc += base * (ktag[X[i]] + 1);
base *= 17;
}
for(int i = 0; i < 25; i++){
if(enc & (1 << i)){
ans += '1';
}
else ans += '0';
}
}
for(int i = 1; i < q; i++){
int enc;
if(qtag[T[i]] == -1) enc = 0;
else enc = kpos[qtag[T[i]]] + 1;
for(int i = 0; i < 9; i++){
if(enc & (1 << i)){
ans += '1';
}
else ans += '0';
}
}
return ans;
}
// g++ -std=gnu++20 -O2 -o grader joisc24_d1C_grader.cpp joisc24_d1C_Aoi.cpp joisc24_d1C_Bitaro.cpp
Compilation message
/usr/bin/ld: /tmp/ccXQO1Zl.o: in function `main':
grader_bitaro.cpp:(.text.startup+0x456): undefined reference to `bitaro(int, int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<long long, std::allocator<long long> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >)'
collect2: error: ld returned 1 exit status
