# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
753613 |
2023-06-05T14:44:21 Z |
hafo |
Toll (BOI17_toll) |
C++14 |
|
118 ms |
157872 KB |
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 16;
const int maxn = 5e4 + 7;
const ll oo = 1e18 + 69;
int k, n, q, m, u, v, w;
struct matrix{
ll a[5][5];
void init() {
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++) a[i][j] = oo;
}
friend matrix operator * (matrix a, matrix b) {
matrix c;
c.init();
for(int i = 0; i < k; i++) {
for(int j = 0; j < k; j++) {
for(int h = 0; h < k; h++) {
mini(c.a[i][j], a.a[i][h] + b.a[h][j]);
}
}
}
return c;
}
};
matrix st[LOG][maxn];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>k>>n>>m>>q;
for(int i = 0; i < LOG; i++)
for(int j = 0; j < n / k; j++) st[i][j].init();
while(m--) {
cin>>u>>v>>w;
st[0][u / k].a[u % k][v % k] = w;
}
for(int i = 1; i < LOG; i++) {
for(int u = 0; u + (1 << i) - 1 <= (n - 1) / k; u++) {
st[i][u] = st[i - 1][u] * st[i - 1][u + (1 << (i - 1))];
}
}
while(q--) {
cin>>u>>v;
if(u / k >= v / k) {
cout<<-1<<"\n";
continue;
}
matrix ans;
for(int i = 0; i < k; i++)
for(int j = 0; j < k; j++) ans.a[i][j] = 0;
int len = v / k - u / k;
int s = u / k;
for(int i = 0; i < LOG; i++)
if((len >> i) & 1) {
matrix cur;
cur.init();
cur = ans * st[i][s];
ans = cur;
s += (1 << i);
}
if(ans.a[u % k][v % k] == oo) cout<<-1;
else cout<<ans.a[u % k][v % k];
cout<<"\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
157872 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
3540 KB |
Output is correct |
6 |
Correct |
3 ms |
3600 KB |
Output is correct |
7 |
Correct |
3 ms |
3540 KB |
Output is correct |
8 |
Correct |
118 ms |
157800 KB |
Output is correct |
9 |
Correct |
115 ms |
157700 KB |
Output is correct |
10 |
Correct |
99 ms |
156928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
79 ms |
80488 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
456 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
456 KB |
Output is correct |
2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
157872 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
3 ms |
3540 KB |
Output is correct |
6 |
Correct |
3 ms |
3600 KB |
Output is correct |
7 |
Correct |
3 ms |
3540 KB |
Output is correct |
8 |
Correct |
118 ms |
157800 KB |
Output is correct |
9 |
Correct |
115 ms |
157700 KB |
Output is correct |
10 |
Correct |
99 ms |
156928 KB |
Output is correct |
11 |
Incorrect |
79 ms |
80488 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |