# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
776197 |
2023-07-07T11:49:02 Z |
MasterTaster |
Toll (BOI17_toll) |
C++14 |
|
3000 ms |
524288 KB |
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define xx first
#define yy second
#define pb push_back
using namespace std;
int n, m, k, q;
map<pair<pii, pii>, int> dp;
int resi(int a, int b, int x, int y)
{
if (dp[{{a, b}, {x, y}}]) return dp[{{a, b}, {x, y}}];
if ((a+1)==b) return 1000000010;
int mid=a+(b-a)/2;
int ress=1000000010;
for (int i=0; i<k; i++)
{
ress=min(ress, resi(a, mid, x, i)+resi(mid, b, i, y));
}
dp[{{a, b}, {x, y}}]=ress;
return ress;
}
int main(){
cin>>k>>n>>m>>q;
for (int i=0; i<m; i++)
{
int u, v, t; cin>>u>>v>>t;
dp[{{u/k, v/k}, {u%k, v%k}}]=t;
}
while (q--)
{
int u, v; cin>>u>>v;
int ress=resi(u/k, v/k, u%k, v%k);
if (ress>=1000000010) cout<<-1<<endl;
else cout<<ress<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3068 ms |
154688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3063 ms |
168984 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
224 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Runtime error |
224 ms |
524288 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3068 ms |
154688 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |