# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
491592 |
2021-12-03T12:26:14 Z |
stefantaga |
Toll (BOI17_toll) |
C++14 |
|
239 ms |
42704 KB |
#include <bits/stdc++.h>
#define INF 1000000000000000
using namespace std;
long long k,n,m,o;
long long rmq[50005][20][5],lg,i,j,t,x,y,cost,locx,locy,p,nivelsf,start,sfarsit;
long long 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<<"-1"<<'\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
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 time |
Memory |
Grader output |
1 |
Correct |
85 ms |
39416 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
3 ms |
972 KB |
Output is correct |
6 |
Correct |
3 ms |
972 KB |
Output is correct |
7 |
Correct |
3 ms |
972 KB |
Output is correct |
8 |
Correct |
86 ms |
39436 KB |
Output is correct |
9 |
Correct |
79 ms |
39428 KB |
Output is correct |
10 |
Correct |
44 ms |
39432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
39408 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
18 ms |
1184 KB |
Output is correct |
8 |
Correct |
19 ms |
1204 KB |
Output is correct |
9 |
Correct |
84 ms |
40456 KB |
Output is correct |
10 |
Correct |
177 ms |
41700 KB |
Output is correct |
11 |
Correct |
129 ms |
41184 KB |
Output is correct |
12 |
Correct |
127 ms |
40676 KB |
Output is correct |
13 |
Correct |
162 ms |
26060 KB |
Output is correct |
14 |
Correct |
96 ms |
25204 KB |
Output is correct |
15 |
Correct |
126 ms |
24900 KB |
Output is correct |
16 |
Correct |
107 ms |
25024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
300 KB |
Output is correct |
6 |
Correct |
2 ms |
1100 KB |
Output is correct |
7 |
Correct |
3 ms |
1100 KB |
Output is correct |
8 |
Correct |
4 ms |
1100 KB |
Output is correct |
9 |
Correct |
3 ms |
1100 KB |
Output is correct |
10 |
Correct |
69 ms |
40220 KB |
Output is correct |
11 |
Correct |
105 ms |
40944 KB |
Output is correct |
12 |
Correct |
145 ms |
41540 KB |
Output is correct |
13 |
Correct |
167 ms |
41828 KB |
Output is correct |
14 |
Correct |
126 ms |
41220 KB |
Output is correct |
15 |
Correct |
96 ms |
24948 KB |
Output is correct |
16 |
Correct |
93 ms |
24892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
300 KB |
Output is correct |
6 |
Correct |
2 ms |
1100 KB |
Output is correct |
7 |
Correct |
3 ms |
1100 KB |
Output is correct |
8 |
Correct |
4 ms |
1100 KB |
Output is correct |
9 |
Correct |
3 ms |
1100 KB |
Output is correct |
10 |
Correct |
69 ms |
40220 KB |
Output is correct |
11 |
Correct |
105 ms |
40944 KB |
Output is correct |
12 |
Correct |
145 ms |
41540 KB |
Output is correct |
13 |
Correct |
167 ms |
41828 KB |
Output is correct |
14 |
Correct |
126 ms |
41220 KB |
Output is correct |
15 |
Correct |
96 ms |
24948 KB |
Output is correct |
16 |
Correct |
93 ms |
24892 KB |
Output is correct |
17 |
Correct |
118 ms |
40984 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
0 ms |
204 KB |
Output is correct |
22 |
Correct |
0 ms |
204 KB |
Output is correct |
23 |
Correct |
7 ms |
1076 KB |
Output is correct |
24 |
Correct |
7 ms |
1100 KB |
Output is correct |
25 |
Correct |
9 ms |
1100 KB |
Output is correct |
26 |
Correct |
8 ms |
1100 KB |
Output is correct |
27 |
Correct |
71 ms |
40260 KB |
Output is correct |
28 |
Correct |
155 ms |
41572 KB |
Output is correct |
29 |
Correct |
185 ms |
41808 KB |
Output is correct |
30 |
Correct |
140 ms |
41256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
85 ms |
39416 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
3 ms |
972 KB |
Output is correct |
6 |
Correct |
3 ms |
972 KB |
Output is correct |
7 |
Correct |
3 ms |
972 KB |
Output is correct |
8 |
Correct |
86 ms |
39436 KB |
Output is correct |
9 |
Correct |
79 ms |
39428 KB |
Output is correct |
10 |
Correct |
44 ms |
39432 KB |
Output is correct |
11 |
Correct |
125 ms |
39408 KB |
Output is correct |
12 |
Correct |
0 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
0 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
0 ms |
204 KB |
Output is correct |
17 |
Correct |
18 ms |
1184 KB |
Output is correct |
18 |
Correct |
19 ms |
1204 KB |
Output is correct |
19 |
Correct |
84 ms |
40456 KB |
Output is correct |
20 |
Correct |
177 ms |
41700 KB |
Output is correct |
21 |
Correct |
129 ms |
41184 KB |
Output is correct |
22 |
Correct |
127 ms |
40676 KB |
Output is correct |
23 |
Correct |
162 ms |
26060 KB |
Output is correct |
24 |
Correct |
96 ms |
25204 KB |
Output is correct |
25 |
Correct |
126 ms |
24900 KB |
Output is correct |
26 |
Correct |
107 ms |
25024 KB |
Output is correct |
27 |
Correct |
0 ms |
204 KB |
Output is correct |
28 |
Correct |
0 ms |
204 KB |
Output is correct |
29 |
Correct |
0 ms |
204 KB |
Output is correct |
30 |
Correct |
0 ms |
204 KB |
Output is correct |
31 |
Correct |
0 ms |
300 KB |
Output is correct |
32 |
Correct |
2 ms |
1100 KB |
Output is correct |
33 |
Correct |
3 ms |
1100 KB |
Output is correct |
34 |
Correct |
4 ms |
1100 KB |
Output is correct |
35 |
Correct |
3 ms |
1100 KB |
Output is correct |
36 |
Correct |
69 ms |
40220 KB |
Output is correct |
37 |
Correct |
105 ms |
40944 KB |
Output is correct |
38 |
Correct |
145 ms |
41540 KB |
Output is correct |
39 |
Correct |
167 ms |
41828 KB |
Output is correct |
40 |
Correct |
126 ms |
41220 KB |
Output is correct |
41 |
Correct |
96 ms |
24948 KB |
Output is correct |
42 |
Correct |
93 ms |
24892 KB |
Output is correct |
43 |
Correct |
118 ms |
40984 KB |
Output is correct |
44 |
Correct |
1 ms |
204 KB |
Output is correct |
45 |
Correct |
1 ms |
204 KB |
Output is correct |
46 |
Correct |
0 ms |
204 KB |
Output is correct |
47 |
Correct |
0 ms |
204 KB |
Output is correct |
48 |
Correct |
0 ms |
204 KB |
Output is correct |
49 |
Correct |
7 ms |
1076 KB |
Output is correct |
50 |
Correct |
7 ms |
1100 KB |
Output is correct |
51 |
Correct |
9 ms |
1100 KB |
Output is correct |
52 |
Correct |
8 ms |
1100 KB |
Output is correct |
53 |
Correct |
71 ms |
40260 KB |
Output is correct |
54 |
Correct |
155 ms |
41572 KB |
Output is correct |
55 |
Correct |
185 ms |
41808 KB |
Output is correct |
56 |
Correct |
140 ms |
41256 KB |
Output is correct |
57 |
Correct |
239 ms |
42704 KB |
Output is correct |
58 |
Correct |
92 ms |
40292 KB |
Output is correct |
59 |
Correct |
142 ms |
41284 KB |
Output is correct |