Submission #1134981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134981		prady	Toll (BOI17_toll)	C++20	0 / 100	30 ms	29620 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define f(i, n) for (ll i = 0; i < n; i++)
#define ia(a, n) \
    ll a[n];     \
    f(i, n) cin >> a[i]
#define iv(v, n)     \
    vector<ll> v(n); \
    f(i, n) cin >> v[i]
#define MOD (1000000007)
#define INF 1000000000000000000LL // Infinity for ll
#define mp make_pair
#define nline '\n'
#define yes cout << "YES\n"
#define no cout << "NO\n"

template <typename T>
using os = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T>
using oms = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// read question properly
// don't forget newlines!!!!!!
// take care about cin >> t;
// comment the optimization before debugging
// ALWAYS USE FIXED << SETPRECISION WHILE OUTPUTTING FLOATS

struct Mat
{
    vector<vector<ll>> mat;
    Mat() {}
    void resize(int n)
    {
        mat.assign(n, vector<ll>(n, INF));
    }
    Mat operator+(const Mat &other)
    {
        ll n = mat.size();
        assert(n == other.mat.size());
        assert(n > 0);
        Mat ans;
        ans.resize(n);
        f(i, n)
        {
            f(j, n)
            {
                ans.mat[i][j] = INF;
                f(k, n)
                {
                    ans.mat[i][j] = min(ans.mat[i][j], mat[i][k] + other.mat[k][j]);
                }
            }
        }
        return ans;
    }
};

void solve()
{
    ll k, n, m, o;
    cin >> k >> n >> m >> o;
    vector<array<ll, 3>> edges;
    f(i, m)
    {
        ll a, b, t;
        cin >> a >> b >> t;
        edges.push_back({a, b, t});
    }

    ll g = (n + k - 1) / k;

    ll L = log2(g);

    Mat lift[L + 1][g];

    f(i, g)
    {
        lift[0][i].resize(k);
    }
    for (auto &x : edges)
    {
        lift[0][x[0] / k].mat[x[0] % k][x[1] % k] = x[2];
    }

    for (ll i = 1; i <= L; i++)
    {
        f(j, g)
        {
            if (j + (1 << (i - 1)) >= g)
                break;
            lift[i][j] = lift[i - 1][j] + lift[i - 1][j + (1 << (i - 1))];
        }
    }

    while (o--)
    {
        ll a, b;
        cin >> a >> b;
        if (a == b)
        {
            cout << 0 << nline;
            continue;
        }
        if (a > b)
        {
            cout << -1 << nline;
            continue;
        }
        if (a / k == b / k)
        {
            cout << -1 << nline;
            continue;
        }
        ll ga = a / k, gb = b / k;
        Mat ans;
        ans.resize(k);
        f(i, k)
        {
            ans.mat[i][i] = 0;
        }
        for (ll i = L; i >= 0; i--)
        {
            if (gb - ga >= (1 << i))
            {
                ans = ans + lift[i][ga];
                ga += (1 << i);
            }
        }
        if(ans.mat[a % k][b % k] != INF) {
            cout << ans.mat[a % k][b % k] << nline;
        }
        else{
            cout << -1 << nline;
        }
    }
}

int main()
{
#ifdef PRADY
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    clock_t T = clock();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long t = 1;
    // cin >> t;

    while (t--)
    {
        solve();
    }

#ifdef PRADY
    cout << "\nTime taken: " << ((float)(clock() - T)) / CLOCKS_PER_SEC << " seconds";
#endif
    return 0;
}

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