Submission #1161357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161357		hahahoang132	Toll (BOI17_toll)	C++20	100 / 100	113 ms	10376 KiB

toll

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ll N = 1e5 + 5;
const ll mod = 1e9 + 7;
const ll inf = LLONG_MAX/5;
#define bit(x,y) ((x >> y) & 1)
vector<pair<ll,ll>> a[N];
const ll bs = 600;
ll l[N],r[N],d[N][6],b[N];
ll ans[N];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll k,n,m,q;
    cin >> k >> n >> m >> q;
    ll i,j;
    for(i = 1;i <= m;i++)
    {
        ll u,v,t;
        cin >> u >> v >> t;
        u++;
        v++;
        a[v].push_back({u,t});
    }
    for(i = 1;i <= n;i++)
    {
        for(j = 0;j < k;j++) d[i][j] = inf;
    }
    ll n2 = 0;
    for(i = 1;i <= n;i += bs)
    {
        l[++n2] = i;
        r[n2] = min(n,i + bs - 1);
        for(j = l[n2];j <= r[n2];j++)
        {
            b[j] = n2;
        }
    }
    for(i = n2;i >= 1;i--)
    {
        for(j = 0;j < k;j++) d[l[i] + j][j] = 0;
        for(j = l[i];j <= r[i];j++)
        {
            ll x = j;
            for(auto tmp : a[x])
            {
                ll y = tmp.first;
                ll add = tmp.second;
                for(ll o = 0;o < k;o++) d[x][o] = min(d[x][o],d[y][o] + add);
            }
        }
    }
    for(i = 1;i <= n;i++) ans[i] = inf;
    vector<ll> del;
    while(q--)
    {
        ll s,e;
        cin >>s  >> e;
        s++;
        e++;
        if(b[s] == b[e])
        {
            ans[s] = 0;
            del.push_back(s);
            for(i = s + 1;i <= e;i++)
            {
                del.push_back(i);
                for(auto tmp : a[i])
                {
                    ll y = tmp.first;
                    ll add = tmp.second;
                    ans[i] = min(ans[i],ans[y] + add);
                }
            }
        }else
        {
            ans[s] = 0;
            del.push_back(s);
            for(i = s + 1;i <= r[b[s]];i++)
            {
                del.push_back(i);
                for(auto tmp : a[i])
                {
                    ll y = tmp.first;
                    ll add = tmp.second;
                    ans[i] = min(ans[i],ans[y] + add);
                }
            }
            for(i = b[s] + 1;i < b[e];i++)
            {
                for(j = l[i];j < l[i] + k;j++)
                {
                    del.push_back(j);
                    for(auto tmp : a[j])
                    {
                        ll y  = tmp.first;
                        ll add = tmp.second;
                        ans[j] = min(ans[j],ans[y] + add);
                    }
                }
                for(j = r[i] - k + 1;j <= r[i];j++)
                {
                    del.push_back(j);
                    for(ll t = 0;t < k;t++)
                    {
                        ans[j] = min(ans[j],d[j][t] + ans[l[i] + t]);
                    }
                }
            }
            for(i = l[b[e]];i <= e;i++)
            {
                del.push_back(i);
                for(auto tmp : a[i])
                {
                    ll y = tmp.first;
                    ll add = tmp.second;
                    ans[i] = min(ans[i],ans[y] + add);
                }
            }
        }
        if(ans[e] == inf) cout << -1;
        else cout << ans[e];
        cout << "\n";
        while(del.size() > 0)
        {
            ans[del.back()] = inf;
            del.pop_back();
        }
    }
}

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