Submission #1156799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156799		Ludissey	Toll (BOI17_toll)	C++20	100 / 100	992 ms	15516 KiB

toll

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int k,n,m,o; cin >> k >> n >> m >> o;
    int sq=sqrt(n);
    vector<vector<pair<int,int>>> neigh(n+k*2+sq);
    vector<vector<pair<int,int>>> ineigh(n+k*2+sq);
    for (int i = 0; i < m; i++)
    {
        int a,b,t; cin >> a >> b >> t;
        neigh[a].push_back({b,t});
        ineigh[b].push_back({a,t});
    }
    vector<vector<pair<pair<int,int>,int>>> query(sq+2);
    for (int i = 0; i < o; i++)
    {
        int a,b; cin >> a >> b;
        query[a/sq].push_back({{a,b},i});
    }
    vector<int> ans(o,-1);
    for (int i = 0; i <= sq+1; i++)
    {
        int mx=((i+1)*sq)-1;
        mx=((mx+k)/k)*k-1;
        vector<vector<int>> dist(k,vector<int>(n+k*2+sq,1e12));
        vector<vector<int>> visited(k,vector<int>(n+k*2+sq,0));
        for (int j = mx-k+1; j <= mx; j++)
        {
            int jk=j-(mx-k+1);
            dist[jk][j]=0;
            int l=mx-k+1;
            while(l<n){
                for (int jl = l; jl < l+k; jl++){
                    for (auto u : neigh[jl])
                    {
                        dist[jk][u.first]=min(dist[jk][u.first], dist[jk][jl]+u.second);
                    }
                }
                l+=k;
            }
            l=mx-k+1;
            while(l>=0){
                for (int jl = l; jl < l+k; jl++){
                    for (auto u : ineigh[jl])
                    {
                        dist[jk][u.first]=min(dist[jk][u.first], dist[jk][jl]+u.second);
                    }
                }
                l-=k;
            }
        }
        vector<int> sdist(n+k*2+sq,1e12);
        vector<bool> svisit(n+k*2+sq,0);
        for (auto u : query[i])
        {
            int a=u.first.first,b=u.first.second; 
            if(b<mx-k+1){
                queue<int> toc;
                priority_queue<pair<int,int>> pq;
                pq.push({0,a});
                sdist[a]=0;
                while(!pq.empty()){
                    int x=pq.top().second; pq.pop();
                    if(svisit[x]) continue;
                    svisit[x]=true;
                    toc.push(x);
                    for (auto u : neigh[x])
                    {
                        if(u.first>b) continue;
                        if(sdist[u.first]>sdist[x]+u.second){
                            sdist[u.first]=sdist[x]+u.second;
                            pq.push({-sdist[u.first],u.first});
                        }
                    }
                }
                if(sdist[b]>=1e12) ans[u.second]=-1;
                else ans[u.second]=sdist[b];

                while(!toc.empty()){
                    int u=toc.front(); toc.pop();
                    sdist[u]=1e12;
                    svisit[u]=false;
                }
            }else{
                int mn=1e12;
                for (int j = mx-k+1; j <= mx; j++)
                {
                    mn=min(mn,dist[j-(mx-k+1)][a]+dist[j-(mx-k+1)][b]);
                }
                if(mn>=1e12){
                    mn=-1;
                }
                ans[u.second]=mn;
            }
        }
        
    }
    for (int j = 0; j < o; j++) cout << ans[j] << "\n";
    return 0;
}

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