Submission #749702

#	Time	Username	Problem	Language	Result	Execution time	Memory
749702		eyalz	Cyberland (APIO23_cyberland)	C++17	100 / 100	2152 ms	120132 KiB

cyberland

#include "cyberland.h"
#pragma GCC diagnostic ignored "-Wliteral-suffix"
#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);}




#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 (stderr)

cyberland.cpp: In function 'f64 solve(int, int, int, int, vi, vi, vi, vi)':
cyberland.cpp:382: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]
  382 |         while(cmult >= visited[cnode].size())visited[cnode].pub(0);
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:395:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  395 |                 while(nmult >= dist[nnode].size()) dist[nnode].pub(INF);
      |                       ~~~~~~^~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:414:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<double>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  414 |             while(nmult >= dist[nnode].size()) dist[nnode].pub(INF);
      |                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 19 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 29 / 29
• Subtask 8: 3 / 3