# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
932210 |
2024-02-23T05:36:34 Z |
LOLOLO |
Toll (BOI17_toll) |
C++14 |
|
120 ms |
39144 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 5e4 + 10;
int k;
vector <pair <int, int>> ed[N];
struct node{
int l, r;
vector < vector <ll>> D;
void ass(int L, int R) {
l = L;
r = R;
D.assign(k * 2, vector <ll> (k * 2, 1e16));
for (int i = 0; i < k * 2; i++) {
for (int j = 0; j < k * 2; j++) {
if (l + i == r - j)
D[i][j] = 0;
}
}
}
void process() {
for (int i = 0; i < k * 2; i++) {
for (int j = i; j < k * 2; j++) {
if (j + l <= r && D[i][r - j - l] < 1e16) {
for (auto x : ed[j + l]) {
if (x.f <= r) {
D[i][r - x.f] = min(D[i][r - j - l] + x.s, D[i][r - x.f]);
}
}
}
}
}
}
} seg[N * 4];
node add(node &L, node &R) {
node M;
M.ass(L.l, R.r);
for (int i = 0; i < k * 2; i++) {
for (int j = 0; j < k * 2; j++) {
for (int f = 0; f < k * 2; f++) {
int id = L.r - f;
if (id >= L.l && i + L.l <= L.r && L.D[i][f] < 1e16) {
for (auto x : ed[id]) {
if (x.f >= R.l) {
M.D[i][j] = min(M.D[i][j], L.D[i][f] + x.s + R.D[x.f - R.l][j]);
}
}
} else {
if (i + L.l > L.r) {
for (int j = 0; j < k * 2; j++)
M.D[i][j] = min(M.D[i][j], R.D[i + L.l - R.l][j]);
}
}
}
}
}
return M;
}
void build(int id, int l, int r) {
if (l == r) {
seg[id].ass(l, r);
return;
}
int m = (l + r) / 2;
build(id * 2, l, m);
build(id * 2 + 1, m + 1, r);
seg[id] = add(seg[id * 2], seg[id * 2 + 1]);
}
node get(int id, int l, int r, int u, int v) {
if (l >= u && r <= v) {
return seg[id];
}
int m = (l + r) / 2;
if (m >= v)
return get(id * 2, l, m, u, v);
if (m + 1 <= u)
return get(id * 2 + 1, m + 1, r, u, v);
node L = get(id * 2, l, m, u, v), R = get(id * 2 + 1, m + 1, r, u, v);
return add(L, R);
}
ll solve() {
int n, m, q;
cin >> k >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int a, b, t;
cin >> a >> b >> t;
a++;
b++;
ed[a].pb({b, t});
}
build(1, 1, n);
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
a++;
b++;
auto t = get(1, 1, n, a, b);
ll d = t.D[0][0];
if (d >= 1e15) {
d = -1;
}
cout << d << '\n';
}
return 0;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) {
solve();
//cout << solve() << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
21844 KB |
Output is correct |
2 |
Correct |
2 ms |
7768 KB |
Output is correct |
3 |
Correct |
2 ms |
7828 KB |
Output is correct |
4 |
Correct |
2 ms |
7772 KB |
Output is correct |
5 |
Correct |
5 ms |
8028 KB |
Output is correct |
6 |
Correct |
4 ms |
8028 KB |
Output is correct |
7 |
Correct |
5 ms |
8024 KB |
Output is correct |
8 |
Correct |
72 ms |
21852 KB |
Output is correct |
9 |
Correct |
72 ms |
21912 KB |
Output is correct |
10 |
Correct |
59 ms |
20316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
120 ms |
39144 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7772 KB |
Output is correct |
2 |
Incorrect |
2 ms |
7772 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7772 KB |
Output is correct |
2 |
Incorrect |
2 ms |
7772 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
21844 KB |
Output is correct |
2 |
Correct |
2 ms |
7768 KB |
Output is correct |
3 |
Correct |
2 ms |
7828 KB |
Output is correct |
4 |
Correct |
2 ms |
7772 KB |
Output is correct |
5 |
Correct |
5 ms |
8028 KB |
Output is correct |
6 |
Correct |
4 ms |
8028 KB |
Output is correct |
7 |
Correct |
5 ms |
8024 KB |
Output is correct |
8 |
Correct |
72 ms |
21852 KB |
Output is correct |
9 |
Correct |
72 ms |
21912 KB |
Output is correct |
10 |
Correct |
59 ms |
20316 KB |
Output is correct |
11 |
Incorrect |
120 ms |
39144 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |