Submission #491580

#TimeUsernameProblemLanguageResultExecution timeMemory
491580stefantagaToll (BOI17_toll)C++14
7 / 100
143 ms20736 KiB
#include <bits/stdc++.h> #define INF 1000000000 using namespace std; int k,n,m,o; int rmq[50005][20][5],lg,i,j,t,x,y,cost,locx,locy,p,nivelsf,start,sfarsit; int din[10][5]; int main() { #ifdef HOME ifstream cin("date.in"); ofstream cout("date.out"); #endif // HOME cin>>k>>n>>m>>o; lg=log2(n); for (i=0;i<=n;i++) { for (j=0;j<=lg;j++) { for (t=0;t<k;t++) { rmq[i][j][t]=INF; } } } for (i=1;i<=m;i++) { cin>>x>>y>>cost; locx=x%k; locy=y%k; rmq[x][0][locy]=cost; } p=1; for (i=1;i<=lg;i++) { for (j=0;j<=n;j++) { nivelsf=j/k+p; if (nivelsf+p>n/k) { continue; } for (start=0;start<k;start++) { for (sfarsit=0;sfarsit<k;sfarsit++) { rmq[j][i][sfarsit]=min(rmq[j][i-1][start]+rmq[nivelsf*k+start][i-1][sfarsit],rmq[j][i][sfarsit]); } } } p=p*2; } for (;o--;) { int a,b; cin>>a>>b; if (a==b) { cout<<"0"<<'\n'; continue; } int niva,nivb,dif; niva=a/k; nivb=b/k; if (niva>=nivb) { cout<<"0"<<'\n'; continue; } dif=nivb-niva; int p=1; for (i=0;i<k;i++) { if (a%k==i) { din[i][0]=0; } else { din[i][0]=INF; } din[i][1]=INF; } int nivel,pas,acum,inainte; nivel=a/k; pas=0; for (i=0;i<=lg;i++) { if (dif&p) { pas++; acum=pas%2; inainte=1-acum; for (j=0;j<k;j++) { for (t=0;t<k;t++) { din[t][acum]=min(din[t][acum],din[j][inainte]+rmq[nivel*k+j][i][t]); } } for (t=0;t<k;t++) { din[t][inainte]=INF; } nivel=nivel+p; } p=p*2; } if (din[b%k][acum]==INF) { cout<<"-1"<<'\n'; } else { cout<<din[b%k][acum]<<'\n'; } } return 0; }

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:108:26: warning: 'acum' may be used uninitialized in this function [-Wmaybe-uninitialized]
  108 |         if (din[b%k][acum]==INF)
      |             ~~~~~~~~~~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...