Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T>
- using mpq = priority_queue<T, vector<T>, greater<T>>;
- namespace rngs = std::ranges;
- using ll = long long;
- using a2l = array<ll, 2>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- void solve() {
- ll n;
- cin >> n;
- vl cs(n), as(n);
- for (ll i = 1; i < n; ++i)
- cin >> cs[i];
- for (ll i = 1; i < n; ++i)
- cin >> as[i];
- vl dp_move(n, LLONG_MAX / 2);
- dp_move[0] = 0;
- for (ll i = 1; i < n; ++i)
- // for (ll j = max(0ll, i - cs[i]); j < i; ++j) {
- for (ll j = i - 1; j >= max(0ll, i - cs[i]); --j) {
- dp_move[i] = min(dp_move[i], dp_move[j] + 1);
- if (as[j])
- break;
- }
- for (ll i = n - 1; i >= 0; --i) {
- if (as[i]) {
- cout << dp_move[i] << '\n';
- return;
- }
- }
- /*
- vector<vl> dp_to(n, vl(n, LLONG_MAX / 2));
- for (ll i = 0; i < n; ++i)
- for (ll j = max(0ll, i - cs[i]); j <= i; ++j)
- dp_to[j][i] = 1;
- for (ll i = 0; i < n; ++i)
- for (ll j = 0; j < n; ++j) {
- }
- for (ll i = 0; i < n; ++i) {
- dp_to[i][i] = 0;
- for (ll j = i + 1; j < n; ++j) {
- dp[i][j] = min(dp[i][j], );
- }
- }
- */
- }
- void solve_wa() {
- ll n;
- cin >> n;
- /*
- vl cs(n), as(n);
- for (auto &x : cs)
- cin >> x;
- for (auto &x : as)
- cin >> x;
- */
- vl cs(n), as(n);
- for (ll i = 1; i < n; ++i)
- cin >> cs[i];
- for (ll i = 1; i < n; ++i)
- cin >> as[i];
- vector<vl> g(n + 1);
- for (ll i = 0; i < n; ++i)
- for (ll j = max(0ll, i - cs[i]); j < i; ++j)
- g[i].push_back(j);
- vl dist(n, LLONG_MAX / 2);
- dist[0] = 0;
- ll cost = 0;
- auto search = [&](auto &&self, ll u, ll fa) -> ll {
- if (dist[u] != LLONG_MAX / 2)
- return as[u] ? 0 : dist[u];
- ll opt = LLONG_MAX / 2;
- for (auto v : g[u])
- opt = min(opt, self(self, v, u) + 1);
- return dist[u] = opt;
- };
- /*
- for (ll i = n - 1; i > 0; --i) {
- if (as[i] && dist[i] == LLONG_MAX / 2)
- cost += search(search, i, -1);
- }
- */
- for (ll i = 1; i < n; ++i)
- if (as[i] && dist[i] == LLONG_MAX / 2)
- cost += search(search, i, -1);
- dbg(cs);
- dbg(as);
- dbg(dist);
- /*
- for (ll i = 1; i < n; ++i) {
- if (cs[i])
- dfs(dfs, i, -1);
- }
- */
- cout << cost << '\n';
- }
- int main(int argc, char **argv) {
- std::ios::sync_with_stdio(false);
- std::cin.tie(nullptr);
- solve_wa();
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment