# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
708627 |
2023-03-12T05:14:50 Z |
joelgun14 |
Toll (BOI17_toll) |
C++17 |
|
3000 ms |
37988 KB |
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
int main() {
int k, n, m, o;
cin >> k >> n >> m >> o;
vector<pair<int, int>> edges[n + 6];
for(int i = 0; i < m; ++i) {
int a, b, t;
cin >> a >> b >> t;
edges[a].push_back(make_pair(b, t));
}
vector<pair<int, int>> queries[n + 6];
for(int i = 0; i < o; ++i) {
int a, b;
cin >> a >> b;
if(a > b)
swap(a, b);
queries[a].push_back({b, i});
}
int ans[o];
memset(ans, -1, sizeof(ans));
ll min_dist[2][5][n + 5];
memset(min_dist, -1, sizeof(min_dist));
for(int i = n; i >= 0; --i) {
bool x = (bool)((i / k) & 1);
//cout << tmp << " " << i << " " << x << " " << i % k << endl;
for(int j = 0; j <= n; ++j)
min_dist[x][i % k][j] = -1;
for(auto j : edges[i]) {
for(int l = 1; l <= n; ++l) {
cout << i << " " << l << endl;
if(min_dist[x ^ 1][j.fi % k][l] != -1) {
if(min_dist[x][i % k][l] == -1)
min_dist[x][i % k][l] = min_dist[x ^ 1][j.fi % k][l] + j.se;
else
min_dist[x][i % k][l] = min(min_dist[x][i % k][l], min_dist[x ^ 1][j.fi % k][l] + j.se);
cout << i << " " << l << endl;
}
}
}
min_dist[x][i % k][i] = 0;
for(auto j : queries[i]) {
ans[j.se] = min_dist[x][i % k][j.fi];
}
}
for(auto i : ans)
cout << i << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3037 ms |
33692 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3051 ms |
37988 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3037 ms |
33692 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |