#include "september.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 100'000 + 10;
const int INF = 1'000'000'000;
struct FenWick {
int n_node = 0;
int tree[N];
void resize(int n) { n_node = n; for (int i = 0; i < n_node; ++ i) tree[i] = 0; }
FenWick() {};
FenWick(int n) { this->resize(n); };
void Update(int idx, int val) {
for ( ; idx <= n_node; idx += (idx & - idx)) tree[idx] += val;
return;
}
int Query(int idx) {
int res = 0;
for ( ; idx > 0; idx -= (idx & - idx)) res += tree[idx];
return res;
}
int Sum_to(int l, int r) {
if (l > r) return 0;
return Query(r) - Query(l - 1);
}
int kth(int val) {
int res = 0, s = 0;
for (int mask = 30; mask >= 0; -- mask) {
int nxt = res | (1 << mask);
if (nxt < n_node && s + tree[nxt] < val) {
res = nxt;
s += tree[nxt];
}
}
++ res; return res;
}
};
int n, m;
int parent[N];
vector<int> g[N];
int perRem[10][N];
int need[10][N];
namespace Order {
struct que {
int idx;
int l, r, mid;
que() {};
que(int _idx, int _l, int _r) : idx(_idx), l(_l), r(_r) {};
void reCalculate() {
mid = (l + r) >> 1;
}
bool operator<(const que& other) const {
return this->mid < other.mid;
}
};
int cnt;
int in[N], out[N];
void dfs(int u) {
in[u] = ++ cnt;
for (const auto& v : g[u]) dfs(v);
out[u] = cnt;
}
void solve(int perRem[], int res[]) {
cnt = 0;
dfs(1);
vector<que> qq;
for (int i = 1; i < n; ++ i) {
qq.push_back(que(i, 1, n - 1));
qq.back().reCalculate();
res[i] = n - 1;
}
FenWick bit(n);
while (!qq.empty()) {
vector<que> newQQ;
sort(qq.begin(), qq.end());
int last = 1;
for (auto& [idx, l, r, mid] : qq) {
while (last <= mid) {
const auto& u = perRem[last];
bit.Update(in[u], 1);
++ last;
}
int u = perRem[idx];
if (bit.Sum_to(in[u], out[u]) == out[u] - in[u] + 1) {
res[idx] = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
if (l <= r) {
newQQ.push_back(que(idx, l, r));
newQQ.back().reCalculate();
}
}
for (int i = last - 1; i >= 1; -- i) bit.Update(in[perRem[i]], -1);
qq = newQQ;
}
}
}
namespace One {
bool check() {
return (m == 1);
}
struct SegTree {
struct Node {
int val = -INF;
Node() {};
Node(int _val) : val(_val) {};
Node operator + (const Node& other) const {
Node res;
res.val = max(this->val, other.val);
return res;
}
};
int n_node = 0;
Node tree[N << 2];
void resize(int _n) { n_node = _n; for (int i = 0; i <= (n_node << 2); ++ i) tree[i] = Node(); };
SegTree() {};
SegTree(int _n) { this->resize(_n); };
void update(int node, int l, int r, int idx, int val) {
if (l == r) {
tree[node].val = val;
return;
}
int mid = (l + r) >> 1;
if (idx <= mid) update(node << 1, l, mid, idx, val);
else update(node << 1 | 1, mid + 1, r, idx, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
void Update(int idx, int val) {
return update(1, 1, n_node, idx, val);
}
Node query(int node, int l, int r, int L, int R) {
if (l > r || L > R || l > R || L > r) return Node();
if (L <= l && r <= R) return tree[node];
int mid = (l + r) >> 1;
return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R);
}
Node Query(int l, int r) {
return query(1, 1, n_node, l, r);
}
};
vector<int> open[N];
int dp[N];
int solve() {
for (int i = 0; i <= n + 1; ++ i) {
vector<int>().swap(open[i]);
dp[i] = -INF;
}
for (int i = 1; i < n; ++ i) {
open[need[1][i]].push_back(i);
}
dp[0] = 0;
FenWick bit(n);
for (int i = 1; i < n; ++ i) bit.Update(i, 1);
SegTree st(n);
for (int i = 1; i < n; ++ i) {
for (const auto& idx : open[i]) bit.Update(idx, -1);
st.Update(i, dp[i - 1]);
int cnt = bit.Query(i);
int last = bit.kth(cnt) + (cnt != 0);
// cout << cnt << ' ' << last << '\n';
if (last <= i) {
dp[i] = st.Query(last, i).val + 1;
}
}
return dp[n - 1];
}
}
namespace Brute_force {
bool check() {
return (n <= 1'000);
}
unsigned seed = chrono::system_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
ll Rand(ll a, ll b = 1ll * INF * INF) {
return a + rng() % (b - a + 1);
}
bool can[1'010][1'010];
ll base[N];
ll Hash[10][N];
vector<int> open[N];
int exist[N];
int dp[N];
int solve() {
srand(time(nullptr));
for (int i = 0; i <= n + 1; ++ i) {
dp[i] = -INF;
exist[i] = 0;
vector<int>().swap(open[i]);
}
for (int i = 0; i <= n + 1; ++ i) {
for (int j = 0; j <= n + 1; ++ j) {
can[i][j] = false;
}
}
for (int i = 1; i <= n; ++ i) base[i] = Rand(1);
for (int i = 1; i <= m; ++ i) {
for (int j = 1; j < n; ++ j) {
Hash[i][j] = base[perRem[i][j]];
open[need[i][j]].push_back(j);
}
}
for (int i = 1; i < n; ++ i) {
ll xorHash[6];
memset(xorHash, 0, sizeof(xorHash));
for (int j = i; j < n; ++ j) {
for (int k = 1; k <= m; ++ k) {
xorHash[k] ^= Hash[k][j];
}
if (*min_element(xorHash + 1, xorHash + 1 + m) == *max_element(xorHash + 1, xorHash + 1 + m)) {
can[i][j] = true;
}
}
}
dp[0] = 0;
for (int i = 1; i < n; ++ i) {
for (const auto& idx : open[i]) ++ exist[idx];
for (int j = i; j >= 1; -- j) {
if (exist[j] < m) break;
if (can[j][i]) {
// cout << j << ' ' << i << ' ' << dp[i] << ' ' << dp[j - 1] << '\n';
dp[i] = max(dp[i], dp[j - 1] + 1);
}
}
}
return dp[n - 1];
}
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
n = N; m = M;
for (int i = 0; i <= n + 1; ++ i) g[i].clear();
for (int v = 2; v <= n; ++ v) {
int u = F[v - 1] + 1;
g[u].push_back(v);
parent[v] = u;
// cerr << u << ' ' << v << '\n';
}
for (int i = 0; i < m; ++ i) {
for (int j = 0; j < n - 1; ++ j) {
perRem[i + 1][j + 1] = S[i][j] + 1;
// cerr << i + 1 << ' ' << j + 1 << ' ' << perRem[i + 1][j + 1] << ' ' << S[i][j] << '\n';
}
}
for (int i = 1; i <= m; ++ i) {
Order::solve(perRem[i], need[i]);
// for (int j = 1; j <= n; ++ j) cout << need[i][j] << ' ';
}
if (One::check()) {
return One::solve();
}
if (Brute_force::check()) {
return Brute_force::solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12864 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
11868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
