Submission #978210

#	Time	Username	Problem	Language	Result	Execution time	Memory
978210		asdfgrace	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	121 ms	63536 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define pv2(x) dbg(cerr << #x << " = " << x.first << ',' << x.second << '\n')
#define parr(x) dbg(prt(#x << " = { "); for (auto y : x) prt(y << ' '); prt("}\n");)
#define parr2(x) dbg(prt(#x << " = { "); for (auto [y, z] : x) prt(y << ',' << z << "  "); prt("}\n");)
#define parr2d(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr(arr);} prt('\n'));
#define parr2d2(x) dbg(prt(#x << ":\n"); for (auto arr : x) {parr2(arr);} prt('\n'));

const int lg = 20;

/*
tree
block nodes 1 by 1
on each move:
block a node
if you block the node with the cat on it
the cat moves to the MAXIMUM REACHABLE NODE
goal is make cat move as much as possible
note that whatever node you are at, you always have a number of subgraphs
you can break off into
pick the subgraph that yields you the best answer when you go to the max
value inside it
this is kind of the equivalent of blocking every other subgraph, then blocking
this node so you end up in the subgraph you chose
for (each subgraph)
dp[node] = max(dp[node], dp[subgraph] + dist(node, max in subgraph))
how do you get the max in subgraph though
same algo as centroid
if we can impl this in n^2, we get like 31 points
other special cases: path, binary tree
*/

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<int> p(n), at(n);
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
    at[p[i]] = i;
  }
  vector<vector<int>> edges(n);
  bool path = true;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    if (y != x + 1) path = false;
    edges[x].push_back(y);
    edges[y].push_back(x);
  }
  if (path) {
    vector<vector<int>> rmq(n, vector<int>(lg, 0));
    for (int i = 0; i < n; i++) {
      rmq[i][0] = p[i];
    }
    for (int j = 1; j < lg; j++) {
      for (int i = 0; i < n - (1 << j) + 1; i++) {
        rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
      }
    }
    function<int(int, int)> rmx = [&] (int l, int r) {
      int p2 = 31 - __builtin_clz(r - l + 1);
      return max(rmq[l][p2], rmq[r - (1 << p2) + 1][p2]);
    };
    vector<long long> best(n, 0);
    function<void(int, int, int)> dnc = [&] (int l, int r, int k) {
      if (k != l) {
        int kl = at[rmx(l, k - 1)];
        dnc(l, k - 1, kl);
        best[k] = max(best[k], best[kl] + k - kl);
      }
      if (k != r) {
        int kr = at[rmx(k + 1, r)];
        dnc(k + 1, r, kr);
        best[k] = max(best[k], best[kr] + kr - k);
      }
    };
    dnc(0, n - 1, at[n - 1]);
    cout << best[at[n - 1]] << '\n';
  } else {
    cout << 7 << '\n';
  }
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26