#include "cyberland.h"
#pragma GCC diagnostic ignored "-Wliteral-suffix"
#pragma GCC target "tbm,abm,bmi,bmi2"
#include <bits/stdc++.h>
using namespace std;
#define inlineexpr inline constexpr
#define gcd std::__gcd
#define bitsizeof(x) (CHAR_BIT*sizeof(x))
/*
#include <ext/random>
auto seed = chrono::steady_clock::now().time_since_epoch().count();
using rnggen = __gnu_cxx::sfmt216091_64;
*/
inlineexpr int ctoi(const char c)
{
return
('0' <= c && c <= '9')?(c-'0'):
('A' <= c && c <= 'Z')?(c-'A'+10):
('a' <= c && c <= 'z')?(c-'a'+10):
0;
}
template<class T, const char... P>
inlineexpr T stoN()
{
constexpr char p[] = {P...,'\0'};
constexpr size_t s = sizeof...(P);
constexpr bool sign = p[0] == '-';
constexpr bool has_sign = (p[0] == '-' || p[0] == '+');
constexpr bool has_special_radix = p[has_sign] == '0';
constexpr size_t radix_idx = has_sign+has_special_radix;
constexpr int radix =
!has_special_radix?10:
(p[radix_idx] == 'b')?2:
(p[radix_idx] == 'x')?16:
8;
constexpr bool has_letter_radix = ((radix==2)||(radix==16));
constexpr size_t digit_start_idx = radix_idx + has_letter_radix;
T res = 0;
size_t i = digit_start_idx;
if(i >= s)return 0;
for(;i<s;++i)
res = radix*res + ctoi(p[i]);
return (sign?-1:1) * res;
}
using i8 = signed char;
using u8 = unsigned char;
using i16 = short;
using u16 = unsigned short;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using uint = u32;
using lint = i64;
using ulint = u64;
using llint = i128;
using ullint = u128;
inlineexpr i8 operator ""i8(unsigned long long x){return i8(x);}
inlineexpr u8 operator ""u8(unsigned long long x){return u8(x);}
inlineexpr i16 operator ""i16(unsigned long long x){return i16(x);}
inlineexpr u16 operator ""u16(unsigned long long x){return u16(x);}
inlineexpr i32 operator ""i32(unsigned long long x){return i32(x);}
inlineexpr u32 operator ""u32(unsigned long long x){return u32(x);}
inlineexpr i64 operator ""i64(unsigned long long x){return i64(x);}
inlineexpr u64 operator ""u64(unsigned long long x){return u64(x);}
#define DEFINE_LITERAL(type, name) template<char... P> inlineexpr type operator"" name(){return stoN<type,P...>();}
DEFINE_LITERAL(i128, i128)
DEFINE_LITERAL(i128, lll)
DEFINE_LITERAL(i128, LLL)
DEFINE_LITERAL(u128, u128)
DEFINE_LITERAL(u128, ulll)
DEFINE_LITERAL(u128, ULLL)
using f32 = float;
using f64 = double;
using f80 = __float80;
using fex = long double;
using f128 = __float128;
using decimal32 = float __attribute__((mode(SD)));
using d32 = decimal32;
using decimal64 = float __attribute__((mode(DD)));
using d64 = decimal64;
using decimal128 = float __attribute__((mode(TD)));
using d128 = decimal128;
using dloat = f64;
inlineexpr f32 operator ""f32(long double x){return f32(x);}
inlineexpr f64 operator ""f64(long double x){return f64(x);}
inlineexpr f80 operator ""f80(long double x){return f80(x);}
inlineexpr fex operator ""fex(long double x){return fex(x);}
inlineexpr f128 operator ""f128(long double x){return f128(x);}
inlineexpr d32 operator ""d32(long double x){return d32(x);}
inlineexpr d64 operator ""d64(long double x){return d64(x);}
inlineexpr d128 operator ""d128(long double x){return d128(x);}
inlineexpr dloat operator ""dloat(long double x){return dloat(x);}
template<class T> inlineexpr T condneg(T x, bool n){return x^-n;}
template<class T> inlineexpr make_unsigned_t<T> unsign(T x){return x;}
template<class T> inlineexpr T urs(T x, int d){return unsign(x)>>d;}
inlineexpr i32 log2(i32 x){return __builtin_ia32_bsrsi(x);}
inlineexpr i64 log2(i64 x){return __builtin_ia32_bsrdi(x);}
template<class T> inlineexpr i32 clog2(T x){return log2(x-1)+1;}
inlineexpr u16 c16(u8 hi, u8 lo){return (u16(hi)<<8)+lo;}
inlineexpr u32 c32(u16 hi, u16 lo){return (u32(hi)<<16)+lo;}
inlineexpr u64 c64(u32 hi, u32 lo){return (u64(hi)<<32)+lo;}
inlineexpr u128 c128(u64 hi, u64 lo){return (u128(hi)<<64)+lo;}
inlineexpr u8 lo(u16 x){return u8(x);}
inlineexpr u16 lo(u32 x){return u16(x);}
inlineexpr u32 lo(u64 x){return u32(x);}
inlineexpr u64 lo(u128 x){return u64(x);}
inlineexpr u8 hi(u16 x){return u8(x>>8);}
inlineexpr u16 hi(u32 x){return u16(x>>16);}
inlineexpr u32 hi(u64 x){return u32(x>>32);}
inlineexpr u64 hi(u128 x){return u64(x>>64);}
inlineexpr i32 poc(u32 x){return __builtin_popcount(x);}
inlineexpr i32 poc(i32 x){return __builtin_popcount(x);}
inlineexpr i32 poc(u64 x){return __builtin_popcountll(x);}
inlineexpr i32 poc(i64 x){return __builtin_popcountll(x);}
inlineexpr i32 poc(u128 x){return __builtin_popcountll(lo(x))+__builtin_popcountll(hi(x));}
inlineexpr i32 clz(u16 x){return __builtin_ia32_lzcnt_u16(x);}
inlineexpr i32 clz(i16 x){return __builtin_ia32_lzcnt_u16(x);}
inlineexpr i32 clz(u32 x){return __builtin_clz(x);}
inlineexpr i32 clz(i32 x){return __builtin_clz(x);}
inlineexpr i32 clz(u64 x){return __builtin_clzll(x);}
inlineexpr i32 clz(i64 x){return __builtin_clzll(x);}
inlineexpr i32 ctz(u16 x){return __builtin_ia32_tzcnt_u16(x);}
inlineexpr i32 ctz(i16 x){return __builtin_ia32_tzcnt_u16(x);}
inlineexpr i32 ctz(u32 x){return __builtin_ctz(x);}
inlineexpr i32 ctz(i32 x){return __builtin_ctz(x);}
inlineexpr i32 ctz(u64 x){return __builtin_ctzll(x);}
inlineexpr i32 ctz(i64 x){return __builtin_ctzll(x);}
template<class T> inlineexpr i32 clo(T x){return clz(~x);}
template<class T> inlineexpr i32 cto(T x){return ctz(~x);}
template<class T> inlineexpr T mask_bit(int d){return T(1)<<d;}
template<class T> inlineexpr T mask_low(int d){return mask_bit<T>(d)-1;}
template<class T> inlineexpr T mask_high(int d){return ~mask_low<T>(bitsizeof(T)-d);}
template<class T> inlineexpr T mask_between(int s, int e){return mask_low<T>(e)&~mask_low<T>(s);}
template<class T> inlineexpr T isolate_mask(T x, T m){return x&m;}
template<class T> inlineexpr T zero_mask(T x, T m){return x&~m;}
template<class T> inlineexpr T one_mask(T x, T m){return x|m;}
template<class T> inlineexpr T flip_mask(T x, T m){return x^m;}
template<class T> inlineexpr T set_mask(T x, T m, bool v){return x^((-v^x)&m);}
inlineexpr u32 extract_mask(u32 x, u32 m){return __builtin_ia32_pext_si(x,m);}
inlineexpr u64 extract_mask(u64 x, u64 m){return __builtin_ia32_pext_di(x,m);}
inlineexpr u32 deposit_mask(u32 x, u32 m){return __builtin_ia32_pdep_si(x,m);}
inlineexpr u64 deposit_mask(u64 x, u64 m){return __builtin_ia32_pdep_di(x,m);}
template<class T> inlineexpr T ror(T x, int d){return urs(x,d)|(x<<(bitsizeof(x)-d));}
template<class T> inlineexpr T rol(T x, int d){return (x<<d)|urs(x,bitsizeof(x)-d);}
template<class T> inlineexpr T btt(T x, int d){return !!isolate_mask(x,mask_bit<T>(d));}
template<class T> inlineexpr T lsb(T x){return x&-x;}
template<class T> inlineexpr T msb(T x){return T(1)<<log2(x);}
template<class T> inlineexpr T lepow2(T x){return msb(x);}
template<class T> inlineexpr T ltpow2(T x){return lepow2(x-1);}
template<class T> inlineexpr T gepow2(T x){return T(1)<<clog2(x);}
template<class T> inlineexpr T gtpow2(T x){return gepow2(x+1);}
template<class T> inlineexpr bool ispow2(T x){return !(x-lsb(x));}
template<class T, int s = bitsizeof(T), T mask = T(~0)>
struct RBIT{static T result(T x)
{
const int _s = s >> 1;
const T _mask = mask ^ T(mask << _s);
x = ((x&~_mask) >> _s)|((x&_mask) << _s);
return RBIT<T,_s,_mask>::result(x);
}};
template<class T, T mask> struct RBIT<T,1,mask>{static T result(T x){return x;}};
template<class T> constexpr T rbit(T x){return RBIT<make_unsigned_t<T>>::result(x);}
#ifdef LOCAL
#define DEBUG 1
#define ifdbg_(x) x
#define ifndbg_(x)
#else
#define DEBUG 0
#define ifdbg_(x)
#define ifndbg_(x) x
#endif
#define ifdbg if(DEBUG)
#define ifndbg if(!DEBUG)
#define dbginfo ifdbg_("at "<<__func__<<" line "<<__LINE__)
#define dbgloc ifdbg cdbg<<dbginfo<<nl
#define dbg ifdbg cdbg<<dbginfo<<":\t"<<
ostream cdbg(0);
constexpr char nl = '\n';
constexpr char sp = ' ';
constexpr char eq = '=';
constexpr char cm = ',';
#define dammit throw runtime_error("bruh moment");
#define ff first
#define ss second
#define sf second.first
#define tt second.second
#define pub push_back
#define pob pop_back
#define emb emplace_back
#define ety empty()
#define ins insert
#define ers erase
#define sz size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define lobd lower_bound
#define upbd upper_bound
template<int D, class T>
struct tensor : public vector<tensor<D-1,T>>
{
using base = vector<tensor<D-1,T>>;
template<class U, class... Args>
constexpr tensor(U n = U(), Args... args) : base(n,tensor<D-1,T>(args...)){}
constexpr size_t size(int dim = 0)const{return (dim == 0)?base::size():(*this)[0].size(dim-1);}
};
template<class T>
struct tensor<1,T> : public vector<T>
{
using base = vector<T>;
template<class... Args>
constexpr tensor(Args... args) : base(args...){}
constexpr tensor(initializer_list<T> args) : base(args){}
constexpr size_t size(int dim = 0)const{return base::size();}
};
template<class T>
struct revit
{
T& v;
revit(T &_v):v(_v){}
constexpr auto begin()const{return std::rbegin(v);}
constexpr auto cbegin()const{return std::crbegin(v);}
constexpr auto end()const{return std::rend(v);}
constexpr auto cend()const{return std::crend(v);}
constexpr auto rbegin()const{return std::begin(v);}
constexpr auto crbegin()const{return std::cbegin(v);}
constexpr auto rend()const{return std::end(v);}
constexpr auto crend()const{return std::cend(v);}
};
template<class Cmp>
struct compinv
{
template<class T, class U>
inline constexpr bool operator()(const T& lhs, const U& rhs)const{return Cmp()(rhs,lhs);}
};
template<class T, class Cmp>
struct pqueue : std::priority_queue<T,vector<T>,compinv<Cmp>>
{
bool erase(const T& value)
{
auto it = find(this->c.begin(), this->c.end(), value);
if(it == this->c.end())return false;
if(it == this->c.begin())this->pop();
else
{
this->c.erase(it);
make_heap(this->c.begin(), this->c.end(), this->comp);
}
return true;
}
};
template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T, class Cmp>
using pq = pqueue<T,Cmp>;
template<class T>
using pqmin = pqueue<T,less<T>>;
template<class T>
using pqmax = pqueue<T,greater<T>>;
using ii = pair<int,int>;
using iii = pair<int,ii>;
using ll = pair<lint,lint>;
using vi = vec<int>;
using vvi = vvec<int>;
using vii = vec<ii>;
using vvii = vvec<ii>;
using vb = vec<bool>;
using vvb = vvec<bool>;
using vl = vec<lint>;
using dijk = pqmin<pair<lint,int>>;
using str = string;
using vc = vec<char>;
constexpr dloat EPS = numeric_limits<dloat>::epsilon();
#define ifn(x) if(!(x))
#define elif else if
#define elifn else ifn
#define whilen(x) while(!(x))
#define fori(i,e,n) for(int i=e;i<n;++i)
#define forie(i,e,n) for(int i=e;i<=n;++i)
#define forir(i,e,n) for(int i=e;i>n;--i)
#define forier(i,e,n) for(int i=e;i>=n;--i)
#define forl(i,e,n) for(lint i=e;i<n;++i)
#define forle(i,e,n) for(lint i=e;i<=n;++i)
#define forlr(i,e,n) for(lint i=e;i>n;--i)
#define forler(i,e,n) for(lint i=e;i>=n;--i)
#define forea(a,v) for(auto &a:v)
#define forea2(a,a2,v) for(auto &[a,a2]:v)
#define forear(a,v) forea(a,revit(v))
#define forea2r(a,a2,v) forea2(a,a2,revit(v))
#define forit(it,v) for(auto it=v.begin();it!=v.end();++it)
#define foritr(it,v) for(auto it=v.rbegin();it!=v.rend();++it)
template<class T, class E>
istream& operator>>(istream& is, pair<T,E>& h){return is>>h.ff>>h.ss;}
template<class T>
istream& operator>>(istream& is, vec<T>& h){forea(t,h)is>>t;return is;}
template<class T, class E>
ostream& operator<<(ostream& os, const pair<T,E>& h){return os<<h.ff<<sp<<h.ss;}
template<class T>
ostream& operator<<(ostream& os, const vec<T>& h){forea(t,h)os<<t<<'\t';return os;}
template<class T>
ostream& operator<<(ostream& os, const vvec<T>& h){forea(t,h)os<<t<<nl;return os;}
template<class T>
ostream& operator<<(ostream& os, const queue<T>& h){forea(t,h)os<<t<<sp;return os;}
template<class T>
ostream& operator<<(ostream& os, const deque<T>& h){forea(t,h)os<<t<<sp;return os;}
template<class T>
ostream& operator<<(ostream& os, const set<T>& h){forea(t,h)os<<t<<sp;return os;}
template<class T, class U>
ostream& operator<<(ostream& os, const map<T,U>& h){forea2(t,u,h)os<<t<<" = "<<u<<nl;return os;}
constexpr lint MOD = 1e9+7;
constexpr lint MOD2 = 1e9+9;
struct mint
{
lint m,x;
constexpr mint():m(MOD),x(0){}
constexpr mint(lint _x):m(MOD),x((_x+m)%m){}
constexpr mint(lint _x, lint _m):m(_m),x((_x+m)%m){}
template<class U> inlineexpr operator U()const{return x;}
inlineexpr bool operator!()const{return !x;}
inline friend ostream& operator<<(ostream& os, const mint& h){return os<<h.x;}
inline friend istream& operator>>(istream& is, mint& h){is>>h.x;h=mint(h.x,h.m);return is;}
inlineexpr mint operator+()const{return *this;}
inlineexpr mint operator-()const{return mint(-x,m);}
template<class U> inlineexpr mint operator+(const U& h)const{return mint(x+lint(h),m);}
template<class U> inlineexpr mint operator-(const U& h)const{return *this+-h;}
template<class U> inlineexpr mint operator*(const U& h)const{return mint(x*lint(h),m);}
template<class U> constexpr mint operator^(const U& h)const{U p=h;mint r(1,m),a(x,m);for(;p;p>>=1){if(p&1)r*=a;a*=a;}return r;}
constexpr mint operator~()const{return *this^(m-2);}
template<class U> inlineexpr bool operator==(const U& h)const{return x==lint(h);}
template<class U> inlineexpr bool operator!=(const U& h)const{return !(*this==h);}
template<class U> inlineexpr mint& operator+=(const U& h){return *this=*this+h;}
template<class U> inlineexpr mint& operator-=(const U& h){return *this+=-h;}
template<class U> inlineexpr mint& operator*=(const U& h){return *this=*this*h;}
template<class U> constexpr mint& operator^=(const U& h){return *this=*this^h;}
};
inlineexpr mint operator ""m(unsigned long long x){return mint(x);}
#define fastio cin.tie(0)->sync_with_stdio(0);
#define setdbg ifdbg cdbg.rdbuf(cerr.rdbuf());
#define cinfail ifdbg cin.exceptions(cin.failbit);
int n,m,k,h;
vvii cons;
using state = pair<dloat,pair<int,int>>;
using dijq = priority_queue<state,vector<state>,greater<state>>;
constexpr dloat INF = numeric_limits<dloat>::infinity();
f64 solve(int N, int M, int K, int H, vi x, vi y, vi c, vi arr)
{
if(K>100)K = 100;
n = N; m = M; k = K; h = H;
vec<dloat> pow_precomp(k+1);
pow_precomp[0] = 1;
forie(i,1,k)
{
pow_precomp[i] = pow_precomp[i-1]*2.dloat;
}
cons = vvii(N);
fori(i,0,M)
{
cons[x[i]].pub({c[i],y[i]});
cons[y[i]].pub({c[i],x[i]});
}
queue<int> qq;
vb reachable(n,0);
qq.push(0);
whilen(qq.ety)
{
int c = qq.front();qq.pop();
if(reachable[c])continue;
reachable[c] = 1;
if(c == H)continue;
forea2(cost,ne,cons[c])ifn(reachable[ne])
{
qq.push(ne);
}
}
if(!reachable[H])return -1;
vvec<dloat> dist(n);
dist[H].pub(0);
dijq que;
que.push({0,{H,0}});
vvb visited(n);
dloat res = INF;
whilen(que.ety)
{
auto [cdist, _temp1] = que.top();que.pop();
auto [cnode, cmult] = _temp1;
while(cmult >= visited[cnode].size())visited[cnode].pub(0);
if(visited[cnode][cmult]) continue;
visited[cnode][cmult] = 1;
forea2(ncost,nnode,cons[cnode])
{
if(nnode == H || !reachable[nnode]) continue;
int nmult;
int po = arr[nnode];
if(po == 2 && cmult < k)
{
nmult = cmult+1;
while(nmult >= dist[nnode].size()) dist[nnode].pub(INF);
dloat trydist = cdist + dloat(ncost)/pow_precomp[cmult];
if(trydist < dist[nnode][nmult])
{
dist[nnode][nmult] = trydist;
if(po == 0 || nnode == 0)
{
if(trydist < res)res = trydist;
}
else
{
que.push({trydist,{nnode,nmult}});
}
}
}
nmult = cmult;
while(nmult >= dist[nnode].size()) dist[nnode].pub(INF);
dloat trydist = cdist + dloat(ncost)/pow_precomp[cmult];
if(trydist < dist[nnode][nmult])
{
dist[nnode][nmult] = trydist;
if(po == 0 || nnode == 0)
{
if(trydist < res)res = trydist;
}
else
{
que.push({trydist,{nnode,nmult}});
}
}
}
}
#ifdef LOCAL
cout << dist << nl;
#endif // LOCAL
return (res==INF)?-1:f64(res);
}
Compilation message
cyberland.cpp: In function 'f64 solve(int, int, int, int, vi, vi, vi, vi)':
cyberland.cpp:453:21: warning: comparison of integer expressions of different signedness: 'std::tuple_element<1, std::pair<int, int> >::type' {aka 'int'} and 'std::vector<bool, std::allocator<bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
453 | while(cmult >= visited[cnode].size())visited[cnode].pub(0);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:466:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
466 | while(nmult >= dist[nnode].size()) dist[nnode].pub(INF);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:485:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
485 | while(nmult >= dist[nnode].size()) dist[nnode].pub(INF);
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
4048 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 4 |
| 2 |
Halted |
0 ms |
0 KB |
- |
