This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "beechtree.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 3e5 + 5;
const int mod = 998244853;
struct Mint {
int val;
Mint(ll x = 0): val((x % mod + mod) % mod) {;}
Mint operator +(const Mint& x) const { return Mint(val + x.val); }
Mint operator -(const Mint& x) const { return Mint(val - x.val); }
Mint operator *(const Mint& x) const { return Mint((ll)val * x.val); }
Mint operator +=(const Mint& x) { return *this = Mint(val + x.val); }
Mint operator -=(const Mint& x) { return *this = Mint(val - x.val); }
Mint operator *=(const Mint& x) { return *this = Mint((ll)val * x.val); }
Mint operator ^(const int& _b) const {
Mint accum = 1, a = *this;
int b = _b;
while(b) {
accum = (b & 1? accum * a : accum);
a *= a;
b >>= 1;
}
return accum;
}
Mint operator /(const Mint& x) { return Mint((ll)val * (x ^ (mod - 2)).val); }
Mint operator /=(const Mint& x) { return *this = Mint((ll)val * (x ^ (mod - 2)).val); }
};
Mint p[2][nmax];
#define hash bjsefdjhsdsfhoi
struct hash {
Mint v[2];
int len;
hash(Mint a, Mint b, int c) { v[0] = a; v[1] = b; len = c; }
hash(Mint a) { v[0] = a; v[1] = a; len = 1; }
hash() { v[0] = 0; v[1] = 0; len = 0; }
hash operator +(const hash& x) const {
return hash(v[0] * p[0][x.len] + x.v[0], v[1] * p[1][x.len] + x.v[1], len + x.len);
}
hash operator -(const hash& x) const {
return hash(v[0] - p[0][len - x.len] * x.v[0], v[1] - p[1][len - x.len] * x.v[1], len - x.len);
}
hash operator += (const hash& x) { return *this = *this + x; }
hash operator -= (const hash& x) { return *this = *this - x; }
bool operator !=(const hash& x) const {
return v[0].val != x.v[0].val || v[1].val != x.v[1].val || len != x.len;
}
ll operator()() const { return (ll)v[0].val * mod + v[1].val; }
bool operator < (const hash& x) const { return (*this)() < x(); }
bool operator == (const hash& x) const { return (*this)() == x(); }
};
vector<pii> g[nmax];
vector<pii> invg[nmax];
vector<int> P, C;
bool isanc(unordered_set<int>& A, unordered_set<int>& B) {
if(sz(A) < sz(B)) return 0;
for(auto &x : B)
if(!A.count(x)) return 0;
return 1;
}
vector<int> sol;
int area[nmax], pin[nmax], pout[nmax], inp;
hash subarb[nmax];
hash eulerH[nmax], dH[nmax];
pii euler[nmax];
int poz;
void init(int node) {
sort(all(g[node]), [&](auto a, auto b) { return a.second < b.second; });
euler[++poz] = pii{node, 0};
eulerH[poz] = eulerH[poz - 1] + hash(2 * C[node] + 0);
pin[node] = poz + 1;
area[node] = 1;
for(auto [x, c] : g[node])
dH[x] = dH[node] + hash(c), init(x), area[node] += area[x];
pout[node] = poz;
euler[++poz] = pii{node, 1};
eulerH[poz] = eulerH[poz - 1] + hash(2 * C[node] + 1);
}
vector<int> difference(int node, int other) {
vector<int> ass_list;
auto getL = [&](int l, int r) {
return eulerH[r + pin[node]] - eulerH[l + pin[node] - 1];
};
auto getR = [&](int l, int r) {
return eulerH[r + pin[other]] - eulerH[l + pin[other] - 1];
};
auto visit = [&](auto&& self, int nod, int& r) -> void {
//cerr << nod << '\n';
r++;
ass_list.emplace_back(nod);
for(auto [x, c] : g[nod]) self(self, x, r);
r++;
};
int l0 = 0, r0 = 0, END0 = pout[node] - pin[node] + 1, l1 = 0, r1 = 0, END1 = pout[other] - pin[other] + 1;
//cerr << node << ", " << other << '\n';
for(int i = 0; i < END0; i++) cerr << getL(i, i).v[0].val << ' '; cerr << '\n';
for(int i = 0; i < END1; i++) cerr << getR(i, i).v[0].val << ' '; cerr << '\n';
while(l0 < END0 && l1 < END1) {
r0 = l0 - 1, r1 = l1 - 1;
for(int lim = 1 << 18; lim > 0; lim >>= 1) {
if(r0 + lim < END0 && r1 + lim < END1 && getL(l0, r0 + lim)() == getR(l1, r1 + lim)()) r0 += lim, r1 += lim;
}
if(r0 == END0 - 1 || r1 == END1 - 1);
else {
auto [nxt0, t0] = euler[pin[node] + r0 + 1];
auto [nxt1, t1] = euler[pin[other] + r1 + 1];
//cerr << nxt0 << ' ' << t0 << '\t' << nxt1 << ' ' << t1 << '\t' << r0 << ", " << r1 << '\n';
if(t1 == 0 && C[nxt1] < C[nxt0]) return {-1};
if(t0 == 1) return {-1};
visit(visit, nxt0, r0);
}
l0 = r0 + 1;
l1 = r1 + 1;
}
//cerr << "<\\>\n";
if(l0 == END0 && l1 < END1) return {-1};
while(l0 < END0) {
auto [nxt0, t0] = euler[pin[node] + l0];
visit(visit, nxt0, l0);
}
//cerr << "<\\>\n";
return ass_list;
}
#define erset set
struct PartDiff {
map<int, erset<hash>> onlevel;
map<hash, int> inverse;
bool feasable = 1;
void add(int dim, int prevdim, erset<hash> ths) {
if(!feasable) return;
if(onlevel.count(dim)) {
for(auto x : ths) {
if(inverse.count(x) == 0) { feasable = 0; return; }
if(inverse[x] > dim) { feasable = 0; return; }
}
}
else {
auto it = onlevel.upper_bound(dim);
int bigger = -1;
if(it == onlevel.end()); else bigger = it -> first;
for(auto x : ths) {
if(inverse.count(x) == 0) { if(bigger == -1) { ; } else { feasable = 0; return; } }
else {
if(inverse[x] > dim) {
if(inverse[x] == bigger) { onlevel[bigger].erase(x); } // o sa il pun, dar n-are ce cauta aici
else { feasable = 0; return; } // prost
}
else { assert(inverse[x] < dim);
if(inverse[x] > prevdim) { continue; } // nu vreau sa il pun
else { feasable = 0; return; } // prost
}
}
onlevel[dim].emplace(x);
inverse[x] = dim;
}
}
}
void add(PartDiff& x) {
if(!feasable) return;
if(!x.feasable) { feasable = 0; return; }
if(sz(x.inverse) > sz(inverse)) swap(x, *this);
int prv = -1;
for(auto [h, v] : x.onlevel) {
add(h, prv, v);
prv = h;
}
x.onlevel.clear();
x.inverse.clear();
return;
}
};
PartDiff dfs(int node) {
PartDiff mine;
int heavyson = -1;
for(auto &[x, c] : g[node]) {
auto T = dfs(x);
//cout << x << " pula \n" << T.feasable << '\n';
mine.add(T); // asta teoretic e useless ca din superimpozabilitate toate vor fi deja acolo, e mai mult un fel de check :clown:
// oare checkul simplu poate fi facut mai putin cretin thinking thinking
//cout << x << " pula \n" << T.feasable << '\n';
if(heavyson == -1 || area[x] > area[heavyson]) heavyson = x;
//cout << node << ' ' << x << '\t' << mine.feasable << ' ' << T.feasable << '\n';
}
if(sz(g[node]) != sz(invg[node])) { mine.feasable = sol[node] = 0; return mine; }
if(heavyson == -1) {
erset<hash> pl; pl.emplace(hash());
mine.add(1, -1, pl);
}
else {
auto sons = difference(node, heavyson);
if(sz(sons) && sons[0] == -1) { mine.feasable = sol[node] = 0; return mine; }
erset<hash> pl;
for(auto x : sons)
pl.emplace(dH[x] - dH[node]);
mine.add(area[node], area[heavyson], pl);
}
sol[node] = mine.feasable;
return mine;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P_, std::vector<int> C_) {
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
p[0][0] = p[1][0] = 1;
p[0][1] = rng() % (mod - 1000) + 503;
#ifdef DLOCAL
p[0][1] = 10;
#endif
p[1][1] = rng() % (mod - 1200) + 505;
for(int i = 2; i < nmax; i++)
p[0][i] = p[0][i - 1] * p[0][1],
p[1][i] = p[1][i - 1] * p[1][1];
P = P_;
C = C_;
for(int i = 1; i < N; i++) {
g[P[i]].emplace_back(i, C[i]);
invg[P[i]].emplace_back(C[i], -1);
}
for(int i = 0; i < N; i++) sort(all(invg[i])), invg[i].erase(unique(all(invg[i])), end(invg[i]));
sol.assign(N, 0);
init(0);
dfs(0);
return sol;
}
/**
Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/
Compilation message (stderr)
beechtree.cpp: In function 'std::vector<int> difference(int, int)':
beechtree.cpp:123:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
123 | for(int i = 0; i < END0; i++) cerr << getL(i, i).v[0].val << ' '; cerr << '\n';
| ^~~
beechtree.cpp:123:70: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
123 | for(int i = 0; i < END0; i++) cerr << getL(i, i).v[0].val << ' '; cerr << '\n';
| ^~~~
beechtree.cpp:124:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
124 | for(int i = 0; i < END1; i++) cerr << getR(i, i).v[0].val << ' '; cerr << '\n';
| ^~~
beechtree.cpp:124:70: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
124 | for(int i = 0; i < END1; i++) cerr << getR(i, i).v[0].val << ' '; cerr << '\n';
| ^~~~
beechtree.cpp: In function 'PartDiff dfs(int)':
beechtree.cpp:225:67: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
225 | if(sz(g[node]) != sz(invg[node])) { mine.feasable = sol[node] = 0; return mine; }
beechtree.cpp:233:65: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
233 | if(sz(sons) && sons[0] == -1) { mine.feasable = sol[node] = 0; return mine; }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |