| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 914854 |
2024-01-22T18:31:30 Z |
sverma22 |
Toll (BOI17_toll) |
C++17 |
|
34 ms |
16648 KB |
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
int n, k;
struct Info {
int L_idx, R_idx, M_idx;
vector<vector<int> > lef;
int lef_st;
vector<vector<int> > rig;
int rig_st;
};
map<int, Info> info_map;
vector<vector<pair<int, int> > > adj;
vector<vector<pair<int, int> > > rev_adj;
void djikstra_left(int start_node, int st, int en, vector<int>& dist) {
priority_queue<pair<int, int> > pq;
vector<bool> processed(dist.size(), false);
// assert(0 <= start_node - st && start_node - st < dist.size());
dist[start_node - st] = 0;
pq.push({0, start_node});
while(!pq.empty()) {
int a = pq.top().second; pq.pop();
if(processed[a]) continue;
processed[a] = true;
for(auto [b, w] : rev_adj[a]) {
if(b < st || b > en) {
continue;
}
// if(b > a) continue; // avoid exploring too much ya know
assert(0 <= a - st && a - st < dist.size());
assert(0 <= b - st && b - st < dist.size());
if(dist[a - st] + w < dist[b - st]) {
dist[b - st] = dist[a - st] + w;
pq.push({-dist[b - st], b});
}
}
}
}
void djikstra_right(int start_node, int st, int en, vector<int>& dist) {
priority_queue<pair<int, int> > pq;
vector<bool> processed(dist.size(), false);
// assert(0 <= start_node - st && start_node - st < dist.size());
dist[start_node - st] = 0;
pq.push({0, start_node});
while(!pq.empty()) {
int a = pq.top().second; pq.pop();
if(processed[a]) continue;
processed[a] = true;
for(auto [b, w] : adj[a]) {
if(b < st || b > en) {
continue;
}
assert(0 <= a - st && a - st < dist.size());
assert(0 <= b - st && b - st < dist.size());
if(dist[a - st] + w < dist[b - st]) {
dist[b - st] = dist[a - st] + w;
pq.push({-dist[b - st], b});
}
}
}
}
void dvc(int l, int r, int lvl) { // may have to add more params later
if(l == r) return;
int m = (l + r) / 2;
// cout << l << ',' << r << '\n';
info_map[lvl].L_idx = l;
info_map[lvl].R_idx = r;
info_map[lvl].M_idx = m;
vector<vector<int> > &lef = info_map[lvl].lef;
lef.resize(k);
// need to populate our fuckers and do a graph search
// START: l * k -> END: m * k + k - 1
int st = l * k;
int en = (m + 1) * k - 1;
info_map[lvl].lef_st = st;
// cout << st << "->" << en << '\n';
int len = en - st + 1;
for(int start_node = m * k; start_node < m * k + k; start_node++) {
// cout << "START NODE: " << start_node << '\n';
// assert(0 <= start_node - m * k && start_node - m * k < lef.size());
lef[start_node - m * k].resize(len, INT_MAX);
djikstra_left(start_node, st, en, lef[start_node - m * k]);
// for(int node = st; node <= en; node++) {
// int dist = lef[start_node - m * k][node - st];
// if(dist == INT_MAX) {
// cout << -1 << ' ';
// } else cout << dist << ' ';
// }
// cout << '\n';
}
vector<vector<int> > &rig = info_map[lvl].rig;
rig.resize(k);
st = (m + 1) * k;
en = (r + 1) * k - 1;
len = en - st + 1;
info_map[lvl].rig_st = st;
// cout << st << "->" << en << '\n';
for(int start_node = m * k + k; start_node < m * k + 2 * k; start_node++) {
// assert(0 <= start_node - m * k - k && start_node - m * k - k < rig.size());
rig[start_node - m * k - k].resize(len, INT_MAX);
djikstra_right(start_node, st, en, rig[start_node - m * k - k]);
// for(int node = st; node <= en; node++) {
// int dist = rig[start_node - m * k - k][node - st];
// if(dist == INT_MAX) {
// cout << -1 << ' ';
// } else cout << dist << ' ';
// }
// cout << '\n';
}
dvc(l, m, 2 * lvl);
dvc(m + 1, r, 2 * lvl + 1);
}
int query(int a, int b) {
int ai = a / k, bi = b/ k;
int lvl = 1;
while(true) {
int m = info_map[lvl].M_idx;
if(ai <= m && m < bi) {
int best = INT_MAX;
for(int i = m * k; i < m * k + k; i++) {
int lef_cheese = info_map[lvl].lef[i - m * k][a - info_map[lvl].lef_st];
if(lef_cheese == INT_MAX) continue;
for(auto [j, w] : adj[i]) {
int rig_cheese = info_map[lvl].rig[j - m * k - k][b - info_map[lvl].rig_st];
if(rig_cheese == INT_MAX) continue;
best = min(best, lef_cheese + w + rig_cheese);
}
}
if(best == INT_MAX) best = -1;
return best;
} else if(ai > m) { // go to right side
lvl = 2 * lvl + 1;
} else { // go to left side
lvl = 2 * lvl;
}
}
return -1;
}
void solve() {
int m, o;
cin >> k >> n >> m >> o;
adj.resize(n + 1);
rev_adj.resize(n + 1);
for(int i = 0; i < m; i++) {
int a, b, t; cin >> a >> b >> t;
adj[a].push_back({b, t});
rev_adj[b].push_back({a, t});
}
// run the divide and conquer
dvc(0, n / k, 1);
for(int i = 0; i < o; i++) { // process queries
int a, b; cin >> a >> b;
cout << query(a, b) << '\n';
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// #ifndef ONLINE_JUDGE
// freopen("file.txt", "r", stdin);
// #endif
int t = 1; // cin >> t;
while(t--) {
solve();
}
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from toll.cpp:1:
toll.cpp: In function 'void djikstra_left(int64_t, int64_t, int64_t, std::vector<long int>&)':
toll.cpp:38:42: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | assert(0 <= a - st && a - st < dist.size());
| ~~~~~~~^~~~~~~~~~~~~
toll.cpp:39:42: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<long int, long int> >::type' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | assert(0 <= b - st && b - st < dist.size());
| ~~~~~~~^~~~~~~~~~~~~
toll.cpp: In function 'void djikstra_right(int64_t, int64_t, int64_t, std::vector<long int>&)':
toll.cpp:64:42: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | assert(0 <= a - st && a - st < dist.size());
| ~~~~~~~^~~~~~~~~~~~~
toll.cpp:65:42: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<long int, long int> >::type' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | assert(0 <= b - st && b - st < dist.size());
| ~~~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
13304 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
34 ms |
16648 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
13304 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
