| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 698347 |
2023-02-13T08:43:00 Z |
badont |
Toll (BOI17_toll) |
C++17 |
|
98 ms |
34264 KB |
#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using ll = long long;
using ld = long double;
using pii = pair<ll,ll>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
//var
ll T;
void solve() {
ll n, m, k, o;
cin >> k >> n >> m >> o;
vector e(n, vector<pii>()), re(n, vector<pii>());
vector fwd(n, vector<int>(k, 0)), bkwd(n, vector<int>(k, 0));
while (m--) {
ll x, y, t;
cin >> x >> y >> t;
e[x].pb({y, t});
fwd[x][y % k] = t;
re[y].pb({x, y});
bkwd[y][x % k] = t;
}
const ll INF = 1e18;
vector<pii> queries(o);
for (auto& [x, y] : queries) {
cin >> x >> y;
}
vector<int> ans(o);
auto dfs = [&](auto dfs, int l, int r, vector<int>& rel) -> void {
assert(l <= r);
debug(l, r);
if (l == r) {
for (auto& idx : rel) {
ans[idx] = -1;
}
return;
}
int m = (l + r) >> 1;
vector dpl(m - l + 1, vector(k, vector<ll>(k, INF)));
vector dpr(r - m, vector(k, vector<ll>(k, INF)));
vector<int> to_left, to_right;
F0R (i, k) dpl[0][i][i] = dpr[0][i][i] = 0;
for (int lp = m - 1, idx = 1; lp >= l; lp--, idx++) {
F0R (x, k) F0R (y, k) F0R (z, k) {
int start_node = lp * k + x;
if (start_node < n and fwd[start_node][y] != 0) {
dpl[idx][x][z] = min(dpl[idx][x][z],
dpl[idx - 1][y][z] + fwd[start_node][y]
);
}
}
}
///debug("here");
for (int rp = m + 2, idx = 1; rp <= r; rp++, idx++) {
F0R (x, k) F0R (y, k) F0R (z, k) {
int start_node = rp * k + x;
if (start_node < n and bkwd[start_node][y] != 0) {
dpr[idx][x][z] = min(dpr[idx][x][z],
dpr[idx - 1][y][z] + bkwd[start_node][y]
);
}
}
}
debug("here");
for (auto& qid : rel) {
auto& [l, r] = queries[qid];
if (r / k <= m) {
to_left.pb(qid);
} else if (l / k > m) {
to_right.pb(qid);
} else {
int lpos = l / k, lmod = l % k;
int rpos = r / k, rmod = r % k;
ll res = INF;
int lidx = m - lpos;
int ridx = rpos - (m + 1);
//debug(l, r, m, lpos, rpos);
//debug(lidx, ridx);
F0R (i, k) F0R (j, k) {
int start_pos = m * k + i;
if (start_pos < n and fwd[start_pos][j] != 0) {
res = min(res,
dpl[lidx][lmod][i] + fwd[start_pos][j] + dpr[ridx][rmod][j]);
}
}
ans[qid] = (res >= INF ? -1 : res);
}
}
dpl.clear();
dpr.clear();
rel.clear();
dfs(dfs, l, m, to_left);
dfs(dfs, m + 1, r, to_right);
};
vector<int> init(n);
iota(all(init), 0);
dfs(dfs, 0, (n - 1) / k, init);
for (auto& u : ans)
cout << u << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
Compilation message
toll.cpp: In instantiation of 'solve()::<lambda(auto:23, int, int, std::vector<int>&)> [with auto:23 = solve()::<lambda(auto:23, int, int, std::vector<int>&)>]':
toll.cpp:145:31: required from here
toll.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) "zzz"
| ^~~~~
toll.cpp:66:3: note: in expansion of macro 'debug'
66 | debug(l, r);
| ^~~~~
toll.cpp:10:20: warning: statement has no effect [-Wunused-value]
10 | #define debug(...) "zzz"
| ^~~~~
toll.cpp:104:3: note: in expansion of macro 'debug'
104 | debug("here");
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
32204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
98 ms |
34264 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Runtime error |
3 ms |
1108 KB |
Execution killed with signal 11 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
324 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Runtime error |
3 ms |
1108 KB |
Execution killed with signal 11 |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
57 ms |
32204 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
