# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
760286 |
2023-06-17T11:54:10 Z |
mgl_diamond |
Toll (BOI17_toll) |
C++14 |
|
33 ms |
8640 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l; i>=(r); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
const int INF = 1e9;
const int N = 50005;
const int LOG = 17;
using dt = pair<ii, int>;
int k, n, m, o, ret[N];
int f[5][N], g[5][N];
vector<ii> go[N], back[N];
vector<dt> querys;
void divide(int lx, int rx, vector<dt> &ask) {
if (ask.empty()) return;
// cout << "From block " << lx << " to block " << rx << ":\n";
// for(dt x : ask) cout << x.fi.fi << " " << x.fi.se << "\n";
// cout << "---------\n";
// centroid
int mx = (lx+rx)/2;
int st = lx*k, en = min(n, (rx+1)*k);
// reset
// cout << st << " " << en << "\n";
for(int t=0; t<k; ++t) {
for(int i=st; i<en; ++i) {
f[t][i] = g[t][i] = INF;
}
}
int l = mx*k, r = min(n, l+k);
// cout << g[0][12] << "\n";
for(int m=l; m<r; ++m) {
f[m-l][m] = g[m-l][m] = 0;
for(int i=m; i>st; --i) {
for(ii x : back[i]) {
f[m-l][x.fi] = min(f[m-l][x.fi], f[m-l][i] + x.se);
}
}
for(int i=m; i<en-1; ++i) {
for(ii x : go[i]) {
// if (i==5) cout << x.fi << " " << x.se <<
g[m-l][x.fi] = min(g[m-l][x.fi], g[m-l][i] + x.se);
}
}
}
// cout << g[0][12] << "\n";
// cout << f[0][0] << " " << g[0][12] << "\n";
vector<dt> _left, _right;
for(auto x : ask) {
if (x.fi.se/k < lx) _left.emplace_back(x);
else if (x.fi.fi/k > rx) _right.emplace_back(x);
else {
for(int m=l; m<r; ++m) {
ret[x.se] = min(ret[x.se], f[m-l][x.fi.fi] + g[m-l][x.fi.se]);
}
// if (x.se == 1) cout << f[]
}
}
divide(lx, mx-1, _left);
divide(mx+1, rx, _right);
}
void solve() {
cin >> k >> n >> m >> o;
for(int i=1; i<=m; ++i) {
int u, v, t;
cin >> u >> v >> t;
go[u].emplace_back(v, t);
back[v].emplace_back(u, t);
}
for(int i=1; i<=o; ++i) {
int u, v;
cin >> u >> v;
querys.push_back({{u, v}, i});
}
memset(ret, 0x3f, sizeof(ret));
divide(0, (n-1)/k, querys);
for(int i=1; i<=o; ++i) {
if (ret[i] < INF) cout << ret[i] << "\n";
else cout << "-1\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen("input.inp", "r")) {
freopen("input.inp", "r", stdin);
freopen("input.out", "w", stdout);
}
solve();
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:112:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen("input.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen("input.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
7588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
33 ms |
8640 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2772 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
19 ms |
7588 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |