Submission #978210

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
978210	2024-05-09T03:32:42 Z	asdfgrace	Cat Exercise (JOI23_ho_t4)	C++17	41 / 100	121 ms	63536 KB

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.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	452 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	452 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	452 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1884 KB	Output is correct
19	Correct	2 ms	1956 KB	Output is correct
20	Correct	3 ms	1932 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1432 KB	Output is correct

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	452 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1884 KB	Output is correct
19	Correct	2 ms	1956 KB	Output is correct
20	Correct	3 ms	1932 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1432 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Incorrect	2 ms	604 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	452 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1884 KB	Output is correct
19	Correct	2 ms	1956 KB	Output is correct
20	Correct	3 ms	1932 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1432 KB	Output is correct
25	Correct	105 ms	63536 KB	Output is correct
26	Correct	110 ms	61692 KB	Output is correct
27	Correct	108 ms	61604 KB	Output is correct
28	Correct	102 ms	41808 KB	Output is correct
29	Correct	104 ms	41700 KB	Output is correct
30	Correct	121 ms	41808 KB	Output is correct
31	Correct	101 ms	41788 KB	Output is correct

Subtask #6
0 / 23.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Incorrect	348 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #7
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	452 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	596 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	2 ms	1884 KB	Output is correct
19	Correct	2 ms	1956 KB	Output is correct
20	Correct	3 ms	1932 KB	Output is correct
21	Correct	2 ms	1372 KB	Output is correct
22	Correct	2 ms	1372 KB	Output is correct
23	Correct	2 ms	1372 KB	Output is correct
24	Correct	2 ms	1432 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Incorrect	2 ms	604 KB	Output isn't correct
27	Halted	0 ms	0 KB	-

Submission #978210

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 7.0 / 7.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 10.0

Subtask #5 20.0 / 20.0

Subtask #6 0 / 23.0

Subtask #7 0 / 26.0

Subtask #1
7.0 / 7.0

Subtask #2
7.0 / 7.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 10.0

Subtask #5
20.0 / 20.0

Subtask #6
0 / 23.0

Subtask #7
0 / 26.0