| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1198672 | sheercold | September (APIO24_september) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int solve(int n, int m, std::vector<int> p,
std::vector<std::vector<int>> s) {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<int>> tree(n);
for (int i = 1; i < n; i++) {
tree[p[i]].push_back(i);
}
vector<int> mx(n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 1; j++) {
mx[s[i][j]] = max(mx[s[i][j]], j);
}
}
auto dfs = [&](auto&& self, int v) {
for (int nxt : tree[v]) {
if (nxt == p[v]) {
continue;
}
self(self, nxt);
mx[v] = max(mx[v], mx[nxt]);
}
};
dfs(dfs, 0);
vector<int> R(n - 1);
iota(R.begin(), R.end(), 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 1; j++) {
R[j] = max(R[j], mx[s[i][j]]);
}
}
vector<int> v(n - 1, 1);
for (int iter = 0; iter < 30; iter++) {
vector<int> hash(n);
for (int i = 0; i < n; i++) {
hash[i] = rng();
}
vector<int> pref(m);
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
pref[j] ^= hash[s[j][i]];
}
int valid = 1;
for (int j = 1; j < m; j++) {
valid &= pref[j] == pref[j - 1];
}
v[i] &= valid;
}
}
int ans = 0;
for (int i = 0, r = 0; i < n - 1; i++) {
r = max(r, R[i]);
if (r <= i && v[i]) {
++ans;
}
}
return ans;
}