Submission #403591

#TimeUsernameProblemLanguageResultExecution timeMemory
403591lyc족보 (KOI18_family)C++14
44 / 100
3069 ms47820 KiB
#include <bits/stdc++.h> using namespace std; #define TRACE(x) cerr << #x << " :: " << x << endl #define _ << " " << #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(),(x).end() #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define RFOR(i,a,b) for (int i=(a);i>=(b);--i) const int mxN = 3e5+5; const int mxK = 3e5+5; const int inf = 1e9+5; int K; struct Tree { int N; vector<int> g[mxN]; int pa[mxN][14]; int dep[mxN]; void read() { FOR(i,1,N){ int P; cin >> P; g[P].push_back(i); } } void dfs(int u) { FOR(k,1,13) pa[u][k] = (pa[u][k-1] == -1 ? -1 : pa[pa[u][k-1]][k-1]); for (int& v : g[u]) { pa[v][0] = u; dep[v] = dep[u]+1; dfs(v); } } int lca(int a, int b) { if (dep[a] < dep[b]) swap(a,b); RFOR(k,13,0) if (pa[a][k] != -1 && dep[pa[a][k]] >= dep[b]) { a = pa[a][k]; } if (a == b) return a; RFOR(k,13,0) if (pa[a][k] != pa[b][k]) { a = pa[a][k], b = pa[b][k]; } return pa[a][0]; } void run() { memset(pa,-1,sizeof pa); dep[0] = 0; dfs(0); } inline int lcd(int a, int b) { return dep[lca(a,b)]; } } A, B; struct node { int s, e, m, v; node *l, *r; node (int s, int e): s(s), e(e), m((s+e)/2), v(inf) { if (s != e) { l = new node(s,m); r = new node(m+1,e); } } void update(int a, int b) { if (s == e) { v = min(v,b); return; } if (a <= m) l->update(a,b); else r->update(a,b); v = min(l->v,r->v); } int qmin(int a, int b) { if (s == a && e == b) return v; if (b <= m) return l->qmin(a,b); if (a > m) return r->qmin(a,b); return min(l->qmin(a,m), r->qmin(m+1,b)); } void reset() { v = inf; if (s == e) return; l->reset(); r->reset(); } } *root; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> A.N >> B.N >> K; A.read(); B.read(); A.run(); B.run(); bool die = 0; root = new node(1,A.N); FOR(i,1,K){ root->reset(); FOR(j,1,K) if (j != i) { int a = A.lcd(i,j), b = B.lcd(i,j); root->update(a,b); } FOR(j,1,K) if (j != i) { int a = A.lcd(i,j), b = B.lcd(i,j); if (a < A.N) die |= b > root->qmin(a+1,A.N); } } cout << (die ? "NO" : "YES") << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...