Submission #1259868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259868		nguyenhuythach	Toll (BOI17_toll)	C++20	100 / 100	125 ms	91460 KiB

toll

//cre:gpt fix
#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=5e4+69;
int n,m,k,q;
vector<pii> adj[nmax];
vector<pii> rev[nmax];
int suf[17][nmax][6],pfx[17][nmax][6];

void input()
{
    cin >> k >> n >> m >> q;
    FOR(i,1,m)
    {
        int u,v,w; cin >> u >> v >> w;
        u++; v++;
        if(u>=1 && u<=n && v>=1 && v<=n){
            adj[u].push_back({v,w});
            rev[v].push_back({u,w});
        }
    }
}

pii pos(int x)
{
    return {(x-1)/k+1,(x-1)%k+1};
}

void dnc(int l,int r,int lv)
{
    if(l>=r) return;
    pii pl = pos(l), pr = pos(r);
    if(pl.fi == pr.fi) return;

    int blockL = pl.fi, blockR = pr.fi;
    int midBlock = (blockL + blockR) / 2;
    int sl = (midBlock - 1) * k + 1;
    int sr = min(n, midBlock * k);
    int tl = sr + 1;
    int tr = min(n, (midBlock + 1) * k);

    FOR(u, l, sr) FOR(c,1,k) suf[lv][u][c] = L;
    FOR(v, tl, r) FOR(c,1,k) pfx[lv][v][c] = L;

    if(tl <= r && sl <= sr){
        int lenMid = sr - sl + 1;
        int lenNext = tr - tl + 1;

        vector<vector<ll>> E(lenMid, vector<ll>(lenNext, (ll)L));
        for(int a = 0; a < lenMid; ++a){
            int u = sl + a;
            FORD(e, adj[u]){
                int v = e.fi; int w = e.se;
                if(v >= tl && v <= tr){
                    int c = v - tl;
                    if((ll)w < E[a][c]) E[a][c] = w;
                }
            }
        }

        for(int a = 0; a < lenMid; ++a){
            int u = sl + a;
            for(int c = 0; c < lenNext; ++c){
                if(E[a][c] != (ll)L) suf[lv][u][c+1] = (int)E[a][c];
            }
        }

        for(int b = midBlock - 1; b >= blockL; --b){
            int start = (b - 1) * k + 1;
            int endd = min(n, b * k);
            for(int u = endd; u >= start; --u){
                FORD(e, adj[u]){
                    int v = e.fi; int w = e.se;
                    int vb = (v-1)/k + 1;
                    if(vb != b+1) continue;
                    for(int c = 1; c <= k; ++c){
                        if(suf[lv][v][c] == L) continue;
                        ll cand = (ll)w + (ll)suf[lv][v][c];
                        if(cand < (ll)L && cand < (ll)suf[lv][u][c]) suf[lv][u][c] = (int)cand;
                    }
                }
            }
        }

        for(int v = tl; v <= tr; ++v){
            for(int c = 1; c <= k; ++c) pfx[lv][v][c] = L;
            int offset = v - tl + 1;
            if(offset >=1 && offset <= lenNext) pfx[lv][v][offset] = 0;
        }

        int blockOfR = pos(r).fi;
        for(int b = midBlock + 1; b <= blockOfR; ++b){
            int start = (b - 1) * k + 1;
            int endd = min(n, b * k);
            if(b == blockOfR) break;
            int nextStart = b * k + 1;
            int nextEnd = min(n, (b+1) * k);
            for(int u = start; u <= endd; ++u){
                FORD(e, adj[u]){
                    int v = e.fi; int w = e.se;
                    int vb = (v-1)/k + 1;
                    if(vb != b+1) continue;
                    for(int c = 1; c <= k; ++c){
                        if(pfx[lv][u][c] == L) continue;
                        ll cand = (ll)pfx[lv][u][c] + (ll)w;
                        if(cand < (ll)L && cand < (ll)pfx[lv][v][c]) pfx[lv][v][c] = (int)cand;
                    }
                }
            }
        }
    }

    dnc(l, sr, lv+1);
    dnc(sr+1, r, lv+1);
}

pii find_node(int l,int r,int lv,int lf,int rt)
{
    pii pl = pos(l), pr = pos(r);
    int blockL = pl.fi, blockR = pr.fi;
    if(blockL == blockR) return {-1,-1};
    int midBlock = (blockL + blockR) / 2;
    int sr = min(n, midBlock * k);
    int tl = sr + 1;
    if(lf <= sr && rt >= tl) return {lv, sr};
    if(rt <= sr) return find_node(l, sr, lv+1, lf, rt);
    else return find_node(sr+1, r, lv+1, lf, rt);
}

void solve()
{
    FOR(i,0,16) FOR(j,1,n) FOR(x,1,5)
    {
        suf[i][j][x]=L;
        pfx[i][j][x]=L;
    }
    dnc(1,n,1);
    
    while(q--)
    {
        int l,r; cin >> l >> r;
        l++; r++;
        pii save=find_node(1,n,1,l,r);
        int mid=save.se;
        int lv=save.fi;
        int ans=L;
        if(pos(l).fi+1==pos(r).fi)
        {
            FORD(i,adj[l]) if(i.fi==r) ans=i.se;
        }
        else
        {
            if(lv==-1){ cout << -1 << '\n'; continue; }
            int midBlock = mid / k;
            int tl = mid + 1;
            int tr = min(n, (midBlock+1)*k);
            int lenNext = tr - tl + 1;
            FOR(c,1,lenNext) {
                if(suf[lv][l][c]!=L && pfx[lv][r][c]!=L){
                    ll cand = (ll)suf[lv][l][c] + (ll)pfx[lv][r][c];
                    if(cand < (ll)ans) ans = (int)cand;
                }
            }
        }
        if(ans==L) cout << -1 << '\n';
        else cout << ans << '\n';
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
    return 0;
}

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