oj.uz

Submission #749702

# Submission time Handle Problem Language Result Execution time Memory
749702 2023-05-28T11:47:42 Z eyalz Cyberland (APIO23_cyberland) C++17
100 / 100
 2152 ms 120132 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 468 KB Correct.
2 Correct 20 ms 476 KB Correct.

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 468 KB Correct.
2 Correct 34 ms 552 KB Correct.
3 Correct 26 ms 516 KB Correct.
4 Correct 26 ms 612 KB Correct.
5 Correct 26 ms 516 KB Correct.
6 Correct 24 ms 2144 KB Correct.
7 Correct 32 ms 2144 KB Correct.
8 Correct 21 ms 4320 KB Correct.
9 Correct 29 ms 340 KB Correct.
10 Correct 27 ms 404 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 504 KB Correct.
2 Correct 20 ms 488 KB Correct.
3 Correct 19 ms 464 KB Correct.
4 Correct 23 ms 340 KB Correct.
5 Correct 23 ms 408 KB Correct.
6 Correct 4 ms 1492 KB Correct.

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8904 KB Correct.
2 Correct 21 ms 468 KB Correct.
3 Correct 20 ms 552 KB Correct.
4 Correct 26 ms 504 KB Correct.
5 Correct 27 ms 404 KB Correct.

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 468 KB Correct.
2 Correct 27 ms 512 KB Correct.
3 Correct 28 ms 520 KB Correct.
4 Correct 34 ms 1940 KB Correct.
5 Correct 24 ms 412 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 532 KB Correct.
2 Correct 19 ms 468 KB Correct.
3 Correct 42 ms 7164 KB Correct.
4 Correct 15 ms 1488 KB Correct.
5 Correct 25 ms 376 KB Correct.
6 Correct 22 ms 464 KB Correct.

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 516 KB Correct.
2 Correct 19 ms 724 KB Correct.
3 Correct 882 ms 42864 KB Correct.
4 Correct 388 ms 8292 KB Correct.
5 Correct 531 ms 17448 KB Correct.
6 Correct 182 ms 8036 KB Correct.
7 Correct 337 ms 10352 KB Correct.
8 Correct 188 ms 1816 KB Correct.
9 Correct 77 ms 704 KB Correct.
10 Correct 61 ms 616 KB Correct.
11 Correct 153 ms 704 KB Correct.
12 Correct 73 ms 596 KB Correct.
13 Correct 75 ms 596 KB Correct.
14 Correct 361 ms 12360 KB Correct.
15 Correct 313 ms 3412 KB Correct.
16 Correct 83 ms 588 KB Correct.
17 Correct 81 ms 596 KB Correct.
18 Correct 75 ms 640 KB Correct.
19 Correct 93 ms 600 KB Correct.
20 Correct 7 ms 340 KB Correct.
21 Correct 6 ms 496 KB Correct.
22 Correct 15 ms 980 KB Correct.

Subtask #8
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 1124 KB Correct.
2 Correct 40 ms 1488 KB Correct.
3 Correct 2091 ms 120132 KB Correct.
4 Correct 414 ms 4784 KB Correct.
5 Correct 1082 ms 47608 KB Correct.
6 Correct 427 ms 18924 KB Correct.
7 Correct 869 ms 22196 KB Correct.
8 Correct 265 ms 1276 KB Correct.
9 Correct 171 ms 1116 KB Correct.
10 Correct 159 ms 1048 KB Correct.
11 Correct 343 ms 728 KB Correct.
12 Correct 170 ms 1092 KB Correct.
13 Correct 180 ms 1104 KB Correct.
14 Correct 2152 ms 47340 KB Correct.
15 Correct 2020 ms 57788 KB Correct.
16 Correct 628 ms 20988 KB Correct.
17 Correct 363 ms 3276 KB Correct.
18 Correct 180 ms 1032 KB Correct.
19 Correct 184 ms 1032 KB Correct.
20 Correct 180 ms 1092 KB Correct.
21 Correct 222 ms 980 KB Correct.
22 Correct 20 ms 480 KB Correct.
23 Correct 16 ms 724 KB Correct.
24 Correct 33 ms 1996 KB Correct.