Submission #1156780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156780		Ludissey	Toll (BOI17_toll)	C++20	25 / 100	2932 ms	9764 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()
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; i++)
    {
        int mx=((i+1)*sq)-1;
        mx=((mx+k)/k)*k-1;
        vector<vector<int>> dist(k,vector<int>(n+k*2,1e9));
        vector<vector<int>> visited(k,vector<int>(n+k*2,0));
        for (int j = mx-k+1; j <= mx; j++)
        {
            int jk=j-(mx-k+1);
            priority_queue<pair<int,pair<int,int>>> pq;
            pq.push({0,{j,2}});
            dist[jk][j]=0;
            while(!pq.empty()){
                int x=pq.top().second.first; int tp=pq.top().second.second; pq.pop();
                if(visited[jk][x]) continue;
                visited[jk][x]=true;
                if(tp==0||tp==2){
                    for (auto u : neigh[x])
                    {
                        if(dist[jk][u.first]>dist[jk][x]+u.second){
                            dist[jk][u.first]=dist[jk][x]+u.second;
                            pq.push({-dist[jk][u.first],{u.first,0}});
                        }
                    }
                }
                if(tp==1||tp==2){
                    for (auto u : ineigh[x])
                    {
                        if(dist[jk][u.first]>dist[jk][x]+u.second){
                            dist[jk][u.first]=dist[jk][x]+u.second;
                            pq.push({-dist[jk][u.first],{u.first,1}});
                        }
                    }
                }
            }
        }
        vector<int> sdist(n+k*2,1e9);
        vector<bool> svisit(n+k*2,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]>=1e9) ans[u.second]=-1;
                else ans[u.second]=sdist[b];

                while(!toc.empty()){
                    int u=toc.front(); toc.pop();
                    sdist[u]=1e9;
                    svisit[u]=false;
                }
            }else{
                int mn=1e9;
                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>=1e9){
                    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: 0 / 31
• Subtask 5: 0 / 44