Submission #1040795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040795		n3rm1n	Toll (BOI17_toll)	C++17	39 / 100	3065 ms	8528 KiB

toll

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll MAXN = 5e4 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

struct querie
{
    ll ql, qr, index;
    querie(){};
    querie(ll _ql, ll _qr, ll _index)
    {
        ql = _ql;
        qr = _qr;
        index = _index;
    }
};
ll k, n, m, q;
vector < pair < ll, ll > > g[MAXN];

void read()
{
    cin >> k >> n >> m >> q;
    ll from, to, cost;
    for (ll i = 1; i <= m; ++ i)
    {
        cin >> from >> to >> cost;
        g[from].push_back(make_pair(to, cost));

    }
}


void queries()
{
    ll ql, qr;
    for (ll i = 1; i <= q; ++ i)
    {
        cin >> ql >> qr;
        int st_bucket = ql/k, fi_bucket = qr/k;
        vector < ll > ans(k, 1e17);
        ans[ql % k] = 0;
        for (int i = st_bucket+1; i <= fi_bucket; ++ i) /// go throught the buckets
        {
            vector < ll > curr(k, 1e17);
            for (int st = 0; st < k; ++ st) ///
            {
                for (auto &[nb, cost]: g[(i-1) * k + st])
                {
                    curr[nb%k] = min(curr[nb%k], cost + ans[st]);
                }
            }
            ans = curr;
        }
        if(ans[qr%k] == 1e17)cout << -1 << endl;
        else cout << ans[qr%k] << endl;
    }

}
int main()
{
    speed();

    read();
    queries();
    return 0;
}

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