Submission #1307916

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307916		StefanSebez	Toll (BOI17_toll)	C++20	17 / 100	250 ms	110696 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;
void chmn(int &x,int y){x=min(x,y);}
vector<pair<int,int>>E[N],E1[N];
int K,n,m,q;
int dist[N];
int 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);
        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+j;
            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);
        if(V/K-U/K<=S+5){
            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);
                }
            }
            int res=dist[V];if(res>=inf)res=-1;
            printf("%i\n",res);
            for(int B=U/K;B<=V/K;B++)for(int i=B*K;i<B*K+K;i++)dist[i]=inf;
        }
        else{
            int res=inf;
            for(int B=0;B*S<=n/K;B++){
                for(int j=0;j<K;j++){
                    int X=B*S+j;
                    if(U<=X&&X<=V)chmn(res,dist1[U][B][j]+dist1[V][B][j]);
                }
            }
            if(res>=inf)res=-1;
            printf("%i\n",res);
        }
    }
    return 0;
}

Compilation message (stderr)

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

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