# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
957634 |
2024-04-04T06:33:41 Z |
12345678 |
Toll (BOI17_toll) |
C++17 |
|
49 ms |
33372 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=5e4+5, kx=16;
ll dp[nx][kx][5], sz, n, m, q, a, b, t;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>sz>>n>>m>>q;
for (int i=0; i<nx; i++) for (int j=0; j<kx; j++) for (int k=0; k<sz; k++) dp[i][j][k]=1e18;
for (int i=0; i<m; i++) cin>>a>>b>>t, dp[a][0][b%sz]=t;
for (int i=1; i<kx; i++) for (int j=0; j<n; j++) for (int k=0; k<sz; k++) for (int l=0; l<sz; l++) dp[j][i][k]=min(dp[j][i][k], dp[j][i-1][l]+dp[min(l+((j/sz)+(1<<(i-1)))*sz, (ll)nx-1)][i-1][k]);
//for (int i=0; i<n; i++) for (int j=0; j<3; j++) for (int k=0; k<sz; k++) cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<'\n';
while (q--)
{
cin>>a>>b;
int c=a/sz, tg=b/sz;
vector<pair<ll, ll>> v;
v.push_back({0, a});
if (c==t)
{
cout<<-1<<'\n';
continue;
}
for (int i=kx-1; i>=0; i--)
{
//cout<<"here "<<c<<' '<<tg<<' '<<c+(1<<i)<<'\n';
if (c+(1<<i)>tg) continue;
if (c+(1<<i)==tg)
{
ll res=1e18;
for (auto x:v) res=min(res, x.first+dp[x.second][i][b%sz]);
if (res==1e18) cout<<-1<<'\n';
else cout<<res<<'\n';
break;
}
vector<ll> tmp(sz, 1e18);
for (int j=0; j<sz; j++) for (auto x:v) tmp[j]=min(tmp[j], x.first+dp[x.second][i][j]);
v.clear();
for (int j=0; j<sz; j++) if (tmp[j]!=1e18) v.push_back({tmp[j], (c+(1<<i))*sz+j});
c+=(1<<i);
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
32600 KB |
Output is correct |
2 |
Correct |
4 ms |
31576 KB |
Output is correct |
3 |
Correct |
5 ms |
31580 KB |
Output is correct |
4 |
Correct |
5 ms |
31580 KB |
Output is correct |
5 |
Correct |
7 ms |
31784 KB |
Output is correct |
6 |
Correct |
6 ms |
31580 KB |
Output is correct |
7 |
Correct |
5 ms |
31656 KB |
Output is correct |
8 |
Correct |
31 ms |
32596 KB |
Output is correct |
9 |
Correct |
29 ms |
32628 KB |
Output is correct |
10 |
Correct |
19 ms |
31836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
33372 KB |
Output is correct |
2 |
Correct |
4 ms |
31580 KB |
Output is correct |
3 |
Incorrect |
6 ms |
31636 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
31580 KB |
Output is correct |
2 |
Incorrect |
6 ms |
31580 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
31580 KB |
Output is correct |
2 |
Incorrect |
6 ms |
31580 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
32600 KB |
Output is correct |
2 |
Correct |
4 ms |
31576 KB |
Output is correct |
3 |
Correct |
5 ms |
31580 KB |
Output is correct |
4 |
Correct |
5 ms |
31580 KB |
Output is correct |
5 |
Correct |
7 ms |
31784 KB |
Output is correct |
6 |
Correct |
6 ms |
31580 KB |
Output is correct |
7 |
Correct |
5 ms |
31656 KB |
Output is correct |
8 |
Correct |
31 ms |
32596 KB |
Output is correct |
9 |
Correct |
29 ms |
32628 KB |
Output is correct |
10 |
Correct |
19 ms |
31836 KB |
Output is correct |
11 |
Correct |
49 ms |
33372 KB |
Output is correct |
12 |
Correct |
4 ms |
31580 KB |
Output is correct |
13 |
Incorrect |
6 ms |
31636 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |