# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
985365 |
2024-05-17T16:59:34 Z |
OAleksa |
Toll (BOI17_toll) |
C++14 |
|
180 ms |
10260 KB |
#include <bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N = 5e4 + 69;
int n, m, k, q, dis[N][6], d[N];
vector<pair<int, int>> g[N];
vector<pair<int, int>> dd[N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> k >> n >> m >> q;
const int B = 100 * k;
for (int i = 0;i < n;i++) {
for (int j = 0;j < k;j++)
dis[i][j] = 1e16;
}
for (int i = 1;i <= m;i++) {
int a, b, c;
cin >> a >> b >> c;
g[a].push_back({b, c});
}
for (int i = 0;i < n;i++) {
int en = (i / B + 1) * B;
d[i] = 0;
int x = min(n, en + k);
for (int j = i + 1;j < x;j++)
d[j] = 1e18;
for (int j = i;j < x;j++) {
for (auto u : g[j]) {
d[u.f] = min(d[u.f], d[i] + u.s);
}
}
--x;
while (x % k != 0) {
dd[i].push_back({x, d[x]});
--x;
}
dd[i].push_back({x, d[x]});
}
while (q--) {
int a, b;
cin >> a >> b;
set<int> st;
st.insert(a);
d[a] = 0;
while (a / B != b / B) {
int en = (a / B + 1) * B;
for (int j = en;j < en + k;j++)
d[j] = 1e18;
while (!st.empty()) {
auto v = *st.begin();
if (v / B == en / B)
break;
st.erase(v);
for (auto u : dd[v]) {
d[u.f] = min(d[u.f], d[v] + u.s);
st.insert(u.f);
}
}
a = en + k - 1;
}
for (int j = a + 1;j <= b;j++)
d[j] = 1e18;
for (int i = a;i < b;i++) {
for (auto u : g[i])
d[u.f] = min(d[u.f], d[i] + u.s);
}
if (d[b] >= 1e18)
cout << "-1\n";
else
cout << d[b] << '\n';
}
}
return 0;
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:68:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
68 | for (int j = a + 1;j <= b;j++)
| ^~~
toll.cpp:70:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
70 | for (int i = a;i < b;i++) {
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
79 ms |
8712 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
180 ms |
10260 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
2 ms |
4540 KB |
Output is correct |
6 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
1 ms |
4700 KB |
Output is correct |
3 |
Correct |
1 ms |
4700 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
2 ms |
4540 KB |
Output is correct |
6 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
79 ms |
8712 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |