// D. Beech Tree
#include<bits/stdc++.h>
#include "beechtree.h"
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
using g_t = vector<vector<int>>;
struct dVal {
unordered_map<int, int> de;
list<set<pair<int, int>>> se;
int seSi;
};
struct unordered_mapsVal {
unordered_map<int, int> maDe;
unordered_map<int, unordered_map<int, unordered_map<int, int>>> maCDe;
unordered_map<int, unordered_map<int, int>> maCat;
unordered_map<int, int> miDe;
unordered_map<int, unordered_map<int, unordered_map<int, int>>> miCDe;
unordered_map<int, unordered_map<int, int>> miCat;
};
struct sdVal {
vector<pair<int, int>> edg;
unordered_map<int, unordered_mapsVal> maV;
};
struct BFSSorting {
int n, actDe, actC, pDe, pC, cat, pO;
};
bool operator<(const BFSSorting &l, const BFSSorting &r) {
return tie(l.actDe, l.pDe, l.actC, l.pC, l.cat, r.pO) < tie(r.actDe, r.pDe, r.actC, r.pC, r.cat, l.pO);
}
vector<int> de;
vector<BFSSorting> de2;
dVal dfs(int n, g_t &g, vector<bool> &po, vector<int> &c) {
unordered_map<int, int> r;
unordered_map<int, vector<pair<int, int>>> ve;
list<set<pair<int, int>>> se;
unordered_map<int, unordered_map<int, int>> OmiR;
int seSi = 0;
for (auto e: g[n]) {
if (r.find(c[e]) != r.end()) po[n] = false;
r[c[e]] = 1;
ve[c[e]] = {};
}
for (auto e: g[n]) {
auto [re, li, ssi] = dfs(e, g, po, c);
if (!po[e]) {
po[n] = false;
}
if (!po[n]) continue;
for (auto &[co, d]: re) {
if (r.find(co) == r.end()) {
po[n] = false;
break;
}
if (co == c[e]) r[c[e]] = d + 1;
ve[co].emplace_back(d, e);
}
if (!po[n]) continue;
if (ssi > seSi) {
swap(se, li);
swap(ssi, seSi);
}
auto itS = se.begin();
for (auto &it: li) {
while (itS != se.end() && itS->size() <= it.size()) {
for (auto cos: *itS) {
if (it.erase(cos) == 0) {
po[n] = false;
break;
}
}
if (!po[n]) break;
itS++;
}
if (!po[n]) break;
if (!it.empty()) {
auto act = se.insert(itS, set<pair<int, int>>());
for (auto cos: it) {
if (itS->erase(cos) == 0) {
po[n] = false;
break;
}
act->insert(cos);
}
}
if (itS != se.end() && itS->empty()) itS++;
if (!po[n]) break;
}
}
if (!po[n]) return {};
se.emplace_back();
for (auto &[co, vec]: ve) {
bool dD = true;
for (auto [d, e]: vec) {
if (d > r[co]) {
po[n] = false;
return {};
} else if (d == r[co]) {
dD = false;
break;
}
}
if (dD) {
se.back().insert({co, r[co]});
seSi++;
}
}
if (se.back().empty()) se.pop_back();
de[n] = seSi;
return {std::move(r), std::move(se), seSi};
}
sdVal sdfs(int n, g_t &g, vector<bool> &po, vector<int> &c, vector<bool> &vis) {
if (vis[n]) return {};
vis[n] = true;
sdVal res;
for (auto e: g[n]) {
auto re = sdfs(e, g, po, c, vis);
if (!po[e]) po[n] = false;
if (!po[n]) continue;
if (re.edg.size() > res.edg.size()) {
swap(re, res);
}
re.edg.emplace_back(e, n);
for (auto &ed: re.edg) {
res.edg.push_back(ed);
auto &ch = de2[ed.first];
auto up = res.maV[ch.actC].miDe.upper_bound(ch.pDe);
if (up != res.maV[ch.actC].miDe.end() && up->second < ch.actDe) {
po[n] = false;
break;
}
if (res.maV[ch.actC].miDe.find(ch.pDe) == res.maV[ch.actC].miDe.end())
res.maV[ch.actC].miDe[ch.pDe] = ch.actDe;
res.maV[ch.actC].miDe[ch.pDe] = min(res.maV[ch.actC].miDe[ch.pDe], ch.actDe);
up = res.maV[ch.actC].miCDe[ch.pC][ch.pDe].upper_bound(de2[ed.second].pDe);
if (up != res.maV[ch.actC].miCDe[ch.pC][ch.pDe].end() && up->second < ch.actDe) {
po[n] = false;
break;
}
if (res.maV[ch.actC].miCDe[ch.pC][ch.pDe].find(de2[ed.second].pDe) == res.maV[ch.actC].miCDe[ch.pC][ch.pDe].end())
res.maV[ch.actC].miCDe[ch.pC][ch.pDe][de2[ed.second].pDe] = ch.actDe;
res.maV[ch.actC].miCDe[ch.pC][ch.pDe][de2[ed.second].pDe] = min(
res.maV[ch.actC].miCDe[ch.pC][ch.pDe][de2[ed.second].pDe], ch.actDe);
up = res.maV[ch.actC].miCat[de2[ed.second].cat].upper_bound(-ch.pO);
if (up != res.maV[ch.actC].miCat[de2[ed.second].cat].end() && up->second < ch.actDe) {
po[n] = false;
break;
}
if (res.maV[ch.actC].miCat[de2[ed.second].cat].find(-ch.pO) == res.maV[ch.actC].miCat[de2[ed.second].cat].end())
res.maV[ch.actC].miCat[de2[ed.second].cat][-ch.pO] = ch.actDe;
res.maV[ch.actC].miCat[de2[ed.second].cat][-ch.pO] = min(res.maV[ch.actC].miCat[de2[ed.second].cat][-ch.pO], ch.actDe);
up = res.maV[ch.actC].maDe.upper_bound(-ch.pDe);
if (up != res.maV[ch.actC].maDe.end() && up->second > ch.actDe) {
po[n] = false;
break;
}
if (res.maV[ch.actC].maDe.find(-ch.pDe) == res.maV[ch.actC].maDe.end())
res.maV[ch.actC].maDe[-ch.pDe] = ch.actDe;
res.maV[ch.actC].maDe[-ch.pDe] = max(res.maV[ch.actC].maDe[-ch.pDe], ch.actDe);
up = res.maV[ch.actC].maCDe[ch.pC][ch.pDe].upper_bound(-de2[ed.second].pDe);
if (up != res.maV[ch.actC].maCDe[ch.pC][ch.pDe].end() && up->second > ch.actDe) {
po[n] = false;
break;
}
if (res.maV[ch.actC].maCDe[ch.pC][ch.pDe].find(-de2[ed.second].pDe) == res.maV[ch.actC].maCDe[ch.pC][ch.pDe].end())
res.maV[ch.actC].maCDe[ch.pC][ch.pDe][-de2[ed.second].pDe] = ch.actDe;
res.maV[ch.actC].maCDe[ch.pC][ch.pDe][-de2[ed.second].pDe] = max(
res.maV[ch.actC].maCDe[ch.pC][ch.pDe][-de2[ed.second].pDe], ch.actDe);
up = res.maV[ch.actC].maCat[de2[ed.second].cat].upper_bound(ch.pO);
if (up != res.maV[ch.actC].maCat[de2[ed.second].cat].end() && up->second > ch.actDe) {
po[n] = false;
break;
}
if (res.maV[ch.actC].maCat[de2[ed.second].cat].find(ch.pO) == res.maV[ch.actC].maCat[de2[ed.second].cat].end())
res.maV[ch.actC].maCat[de2[ed.second].cat][ch.pO] = ch.actDe;
res.maV[ch.actC].maCat[de2[ed.second].cat][ch.pO] = max(res.maV[ch.actC].maCat[de2[ed.second].cat][ch.pO], ch.actDe);
}
}
return res;
}
void bfs(int n, g_t &g, vector<int> &c, vector<bool> &vi) {
int d = 0, col = 0;
BFSSorting la{n, de[n], c[n], de[n], c[n], 0, 1};
priority_queue<BFSSorting> pq;
pq.push({n, de[n], c[n], de[n], c[n], 0, 1});
while (!pq.empty()) {
auto bO = pq.top();
pq.pop();
if (vi[bO.n]) continue;
vi[bO.n] = true;
if (bO.actDe != la.actDe || bO.pDe != la.pDe || bO.pO != la.pO) {
d++;
}
if (bO.actC != la.actC || bO.pC != la.pC || bO.cat != la.cat || bO.actDe != la.actDe || bO.pDe != la.pDe) {
col++;
}
de2[bO.n] = la = {bO.n, bO.actDe, bO.actC, bO.pDe, bO.pC, col, d};
for (auto e: g[bO.n]) {
pq.push({e, de[e], c[e], de[bO.n], c[bO.n], de2[bO.n].cat, de2[bO.n].pO});
}
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
g_t g(N);
for (int i = 1; i < N; ++i) {
g[P[i]].push_back(i);
}
de = vector<int>(N);
de2 = vector<BFSSorting>(N);
vector<bool> po(N, true);
dfs(0, g, po, C);
vector<bool> vis(N, false);
for (int i = 0; i < N; ++i) {
if (po[i]) {
bfs(i, g, C, vis);
}
}
std::fill(vis.begin(), vis.end(), false);
for (int i = 0; i < N; ++i) {
if (po[i]) {
sdfs(i, g, po, C, vis);
}
}
return {po.begin(), po.end()};
}
//#ifndef EVAL
//
//signed main() {
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
// int n, m;
// cin >> n >> m;
// vector<int> p(n), c(n);
// for (auto &e: p) {
// cin >> e;
// }
// for (auto &e: c) {
// cin >> e;
// }
// auto res = beechtree(n, m, p, c);
//// vector<int> ou{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
// for (auto e: res) {
// cout << e << " ";
// }
//// for (int i = 0; i < n; ++i) {
//// if (ou[i] != res[i]) cout << i << " ";
//// }
// cout << "\n";
//}
//
//#endif
Compilation message
beechtree.cpp: In function 'sdVal sdfs(int, g_t&, std::vector<bool>&, std::vector<int>&, std::vector<bool>&)':
beechtree.cpp:141:36: error: 'class std::unordered_map<int, int>' has no member named 'upper_bound'
141 | auto up = res.maV[ch.actC].miDe.upper_bound(ch.pDe);
| ^~~~~~~~~~~
beechtree.cpp:149:47: error: 'std::unordered_map<int, std::unordered_map<int, int> >::mapped_type' {aka 'class std::unordered_map<int, int>'} has no member named 'upper_bound'
149 | up = res.maV[ch.actC].miCDe[ch.pC][ch.pDe].upper_bound(de2[ed.second].pDe);
| ^~~~~~~~~~~
beechtree.cpp:158:52: error: 'std::unordered_map<int, std::unordered_map<int, int> >::mapped_type' {aka 'class std::unordered_map<int, int>'} has no member named 'upper_bound'
158 | up = res.maV[ch.actC].miCat[de2[ed.second].cat].upper_bound(-ch.pO);
| ^~~~~~~~~~~
beechtree.cpp:166:31: error: 'class std::unordered_map<int, int>' has no member named 'upper_bound'
166 | up = res.maV[ch.actC].maDe.upper_bound(-ch.pDe);
| ^~~~~~~~~~~
beechtree.cpp:174:47: error: 'std::unordered_map<int, std::unordered_map<int, int> >::mapped_type' {aka 'class std::unordered_map<int, int>'} has no member named 'upper_bound'
174 | up = res.maV[ch.actC].maCDe[ch.pC][ch.pDe].upper_bound(-de2[ed.second].pDe);
| ^~~~~~~~~~~
beechtree.cpp:183:52: error: 'std::unordered_map<int, std::unordered_map<int, int> >::mapped_type' {aka 'class std::unordered_map<int, int>'} has no member named 'upper_bound'
183 | up = res.maV[ch.actC].maCat[de2[ed.second].cat].upper_bound(ch.pO);
| ^~~~~~~~~~~
