| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 696767 |
2023-02-07T08:16:15 Z |
SOCIOPATE |
Toll (BOI17_toll) |
C++17 |
|
159 ms |
148592 KB |
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define pll pair<ll, ll>
#define pii pair<int, int>
#define pdd pair<ld, ld>
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update> ordset;
#pragma GCC optimize("-O3")
#pragma GCC optimize("unroll-loops")
ll INF = 2e18;
const ll mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll n, ll m){
if(m == 0) return 1ll;
if(m & 1ll) return (n * binpow(n, m - 1ll)) % mod;
ll b = binpow(n, m / 2ll);
return (b*b) % mod;
}
int n, k, m, o;
vector<vector<pll>> b, a;
ll ans[50005][18][20] = {0};
void dq(int l, int r, int lev){
if(l > r) return;
int m = (l + r) / 2;
for(int i = m; i >= l; i--)
for(int j = 0; j <= 3 * k; j++) ans[i][lev][j] = (i == m - j ? 0ll : INF);
for(int i = m + 1; i <= r; i++){
for(int j = 0; j <= 3 * k; j++) ans[i][lev][j] = INF;
for(pll u : b[i])
for(int j = 0; j <= 3 * k; j++) ans[i][lev][j] = min(ans[i][lev][j], ans[u.ff][lev][j] + u.ss);
}
//cout << l << ' ' << r << ' ' << m << ' ' << lev << '\n';
for(int i = m; i >= l; i--){
for(pll u : a[i]){
if(u.ff > m) continue;
//cout << i << ' ' << u.ff << ' ' << u.ss << '\n';
for(int j = 0; j <= 3 * k; j++) ans[i][lev][j] = min(ans[i][lev][j], ans[u.ff][lev][j] + u.ss);
}
}
// for(int i = l; i <= r; i++){
// cout << i << '\n';
// for(int j = 0; j <= 3 * k; j++) cout << ans[i][lev][j] << ' ';
// cout << '\n';
// }
dq(l, m - 1, lev + 1);
dq(m + 1, r, lev + 1);
}
ll ask(int l, int r, int lev, int a, int b){
assert(l <= r);
int m = (l + r) / 2;
if(a <= m && m + 1 <= b){
ll res = INF;
for(int j = 0; j <= 3*k; j++) res = min(res, ans[a][lev][j] + ans[b][lev][j]);
return res;
}
if(a > m) return ask(m + 1, r, lev + 1, a, b);
return ask(l, m - 1, lev + 1, a, b);
}
void solve(){
cin >> k >> n >> m >> o;
a.resize(n);
b.resize(n);
for(int i = 0; i < m; i++){
int u, v, w;
cin >> u >> v >> w;
a[u].push_back({v, w});
b[v].push_back({u, w});
}
dq(0, n - 1, 0);
for(int i = 0; i < o; i++){
int u, v;
cin >> u >> v;
if(u > v){
cout << -1 << '\n';
continue;
}
if(u == v){
cout << 0 << '\n';
return;
}
ll res = ask(0, n - 1, 0, u, v);
cout << (res == INF ? -1 : res) << '\n';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
int tt;
//cin >> tt;
tt = 1;
while (tt--) {
solve();
#ifdef LOCAL
cout << "__________________________________" << endl;
#endif
}
#ifdef LOCAL
cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << "sec" << '\n';
#endif
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
146892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
148592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
146892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
