Submission #403510

#TimeUsernameProblemLanguageResultExecution timeMemory
403510lyc족보 (KOI18_family)C++14
0 / 100
24 ms47340 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; int K; struct Tree { int N; vector<int> g[mxN]; int pa[mxN][14]; int dep[mxN]; int lcd[mxK]; 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); FOR(i,1,K-1){ lcd[i] = dep[lca(i,i+1)]; } } } A, B; const int inf = 1e9+5; int maxV[mxN], minY[mxN], stk[mxN], tp, ls[mxN], rs[mxN]; 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 = 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)); } } *root, *root2, *root3; 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(); tp = 0; root = new node(1,K); FOR(i,1,K){ while (tp > 0 && A.lcd[stk[tp-1]] >= A.lcd[i]) { rs[stk[--tp]] = i-1; } ls[i] = (tp > 0 ? stk[tp-1]+1 : 1); stk[tp++] = i; root->update(i, B.lcd[i]); } while (tp > 0) { rs[stk[--tp]] = A.N; } FOR(i,1,A.N){ maxV[i] = -inf; minY[i] = inf; } FOR(i,1,K-1){ maxV[A.lcd[i]] = max(maxV[A.lcd[i]], B.lcd[i]); minY[A.lcd[i]] = min(minY[A.lcd[i]], root->qmin(ls[i], rs[i])); } root2 = new node(1,A.N); root3 = new node(1,A.N); FOR(i,1,A.N){ root2->update(i, -maxV[i]); root3->update(i, minY[i]); } bool die = 0; FOR(i,2,A.N){ die |= -root2->qmin(1,i-1) > root3->qmin(i,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...