Submission #1222373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222373		j_vdd16	Toll (BOI17_toll)	C++20	49 / 100	163 ms	73740 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#pragma GCC optimize("trapv")

template <typename T1, typename T2>
using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using indexed_set = indexed_map<T, null_type>;

#define loop(x, i) for (int i = 0; i < (x); i++)
#define loop1(x, i) for (int i = 1; i <= (x); i++)
#define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--)
#define itloop(x) for (auto it = begin(x); x != end(x); it++)
#define itrev(x) for (auto it = rbegin(x); x != rend(x); it++)
#define int uint32_t
#define INF ((int64_t)(1e8))
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define removeIn(x, l) l.erase(find(ALL(l), x))
#define pb push_back
#define sz(x) (int)(x).size()
#define F first
#define S second
#define var const auto &
#define foreach(l) for (var e : l)

typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<i32> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vi32> vvi32;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vii> vvii;
typedef vector<viii> vviii;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;
typedef vector<si> vsi;
typedef vector<sii> vsii;
typedef vector<vsi> vvsi;
typedef vector<string> vstr;
typedef vector<vector<string>> vvstr;
typedef vector<bool> vb;
typedef vector<vb> vvb;
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p)
{
    in >> p.first >> p.second;
    return in;
}
template <size_t I = 0, typename... Ts>
typename enable_if<I == sizeof...(Ts), void>::type
read_tuple(tuple<Ts...> &, istream &) {}
template <size_t I = 0, typename... Ts>
    typename enable_if < I<sizeof...(Ts), void>::type read_tuple(tuple<Ts...> &t, istream &in)
{
    in >> get<I>(t);
    read_tuple<I + 1>(t, in);
}
template <typename... Ts>
istream &operator>>(istream &in, tuple<Ts...> &t)
{
    read_tuple(t, in);
    return in;
}
template <typename... Args>
ostream &operator<<(ostream &os, const tuple<Args...> &t)
{
    apply([&os](const Args &...args)
          { size_t n = 0;  ((os << ' ' << args), ...); }, t);
    return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p)
{
    os << p.F << ' ' << p.S;
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (auto &element : vec)
        is >> element;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
    for (auto &element : vec)
        os << element << ' ';
    return os;
}
template <typename... T>
void DBG(T &&...args) { ((cerr << args << ' '), ...) << endl; }
template <typename... T>
void print(T &&...args) { ((cout << args << ' '), ...) << endl; }
template <typename... T>
void read(T &&...args) { ((cin >> args), ...); }

int k = 1, n, m, o;
viii edges;
vii qs;

vi solve()
{
    vvvi p(25, vvi(n, vi(k, INF))); // price
    for (var[a, b, t] : edges)
    {
        p[0][a][b % k] = t;
    }
    for (int j = 1; j < 25; j++)
    {
        loop(n, i)
        {
            int i2 = i - i % k;
            loop(k, dest)
            {
                loop(k, via)
                {
                    int via2 = via + i2 + k * (1 << (j - 1));
                    if (via2 >= n)
                        continue;
                    int p1 = p[j - 1][i][via];
                    int p2 = p[j - 1][via2][dest];
                    if (p1 == INF || p2 == INF)
                        continue;
                    p[j][i][dest] = min(p[j][i][dest], p1 + p2);
                }
            }
        }
    }
    vi res;
    for (auto [a, b] : qs)
    {
        if (b < a)
        {
            print(-1);
            continue;
        }
        int la = a / k, lb = b / k;
        if (la == lb)
        {
            res.pb(-1);
            continue;
        }
        int stepCnt = 0;
        vi cost(k, INF);
        loop(25, j)
        {
            if ((1 << j) & (lb - la))
            {
                vi cost2(k, INF);
                loop(k, dest)
                {
                    if (a + (1 << j) == b && dest != b % k)
                        continue;
                    if (stepCnt == 0)
                    {
                        cost2[dest] = p[j][a][dest];
                        continue;
                    }
                    loop(k, start)
                    {
                        cost2[dest] = min(cost2[dest], cost[start] + p[j][a + start][dest]);
                    }
                }
                if (!stepCnt)
                    a -= a % k;
                swap(cost, cost2);
                a += (1 << j) * k;
                stepCnt++;
            }
        }
        if (cost[b % k] == INF)
            res.pb(-1);
        else
            res.pb(cost[b % k]);
    }

    return res;
}

void run()
{
    read(k, n, m, o);
    qs = vii(o);
    edges = viii(m);
    read(edges);
    read(qs);
    foreach (solve())
    {
        int er = -1;
        if (e == er)
            print(-1);
        else
            print(e);
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    string name = "";
    if (sz(name))
    {
        if (!freopen((name + ".in").c_str(), "r", stdin) || !freopen((name + ".out").c_str(), "w", stdout))
            return 1;
    }
    int t = 1;
    // read(t);
    while (t--)
        run();
}

• Subtask 1: 0 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 0 / 44