Submission #1307927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307927		StefanSebez	Toll (BOI17_toll)	C++20	100 / 100	590 ms	217248 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=5e4+50,S=500,inf=1e9;
const ll INF=1e18;
void chmn(int &x,int y){x=min(x,y);}
void chmn(ll &x,ll y){x=min(x,y);}
vector<pair<int,ll>>E[N],E1[N];
int K,n,m,q;
ll dist[N];
ll dist1[N][N/S+5][5];
int main(){
    scanf("%i%i%i%i",&K,&n,&m,&q);
    for(int i=1;i<=m;i++){
        int u,v,w;scanf("%i%i%i",&u,&v,&w);
        if(u>v)swap(u,v);
        E[u].pb({v,w});
        E1[v].pb({u,w});
    }
    for(int B=0;B*S<=n/K;B++){
        for(int j=0;j<K;j++){
            int U=B*S*K+j;if(U>n)continue;
            for(int i=0;i<=n;i++)dist1[i][B][j]=inf;
            queue<int>kju;kju.push(U);
            dist1[U][B][j]=0;
            while(!kju.empty()){
                int u=kju.front();kju.pop();
                for(auto [v,w]:E[u]){
                    if(dist1[v][B][j]>=inf)kju.push(v);
                    chmn(dist1[v][B][j],dist1[u][B][j]+w);
                }
            }
            kju.push(U);
            while(!kju.empty()){
                int u=kju.front();kju.pop();
                for(auto [v,w]:E1[u]){
                    if(dist1[v][B][j]>=inf)kju.push(v);
                    chmn(dist1[v][B][j],dist1[u][B][j]+w);
                }
            }
        }
    }
    for(int i=0;i<=n;i++)dist[i]=inf;
    while(q--){
        int U,V;scanf("%i%i",&U,&V);
        ll res=inf;bool bul=false;
        for(int B=0;B*S<=n/K;B++){
            for(int j=0;j<K;j++){
                int X=B*S*K+j;
                if(U<=X&&X<=V)chmn(res,dist1[U][B][j]+dist1[V][B][j]),bul=true;
            }
        }
        if(!bul){
            queue<int>kju;kju.push(U);
            dist[U]=0;
            while(!kju.empty()){
                int u=kju.front();kju.pop();
                for(auto [v,w]:E[u])if(v<=V){
                    if(dist[v]>=inf)kju.push(v);
                    chmn(dist[v],dist[u]+w);
                }
            }
            chmn(res,dist[V]);
            for(int B=U/K;B<=V/K;B++)for(int i=B*K;i<B*K+K;i++)dist[i]=inf;
        }
        if(res>=inf)res=-1;
        printf("%lld\n",res);
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%i%i%i%i",&K,&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:20:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         int u,v,w;scanf("%i%i%i",&u,&v,&w);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~
toll.cpp:50:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         int U,V;scanf("%i%i",&U,&V);
      |                 ~~~~~^~~~~~~~~~~~~~

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