Archives
Trending
Support
Login
clear text
XML
Django
JavaScript
MATLAB
C
C++
C#
Python
SQL
Shell
Bash
Markdown
YAML
JSON
HTML
CSS
PHP
Java
Ruby
Go
Rust
Swift
Kotlin
Arduino
TypeScript
Perl
Autohotkey
Lua
SQF
R
Scala
Haskell
Groovy
Dart
Clojure
VB.NET
Objective-C
PowerShell
Bash
CoffeeScript
Verilog
#include
#include
#include
#include
#include
using namespace std; const int maxn = 3e5 + 10; const int logn = 24; int n; int id_node[maxn]; int parent[maxn]; int depth[maxn]; int up_node[maxn][logn]; int LCA(int A, int B) { if(depth[A] < depth[B]) { swap(A, B); } for(int i = logn - 1; i >= 0; i--) { if(depth[A] - (1 << i) >= depth[B]) { A = up_node[A][i]; } } if(A == B) { return A; } for(int i = logn - 1; i >= 0; i--) { if(up_node[A][i] != -1 and up_node[A][i] != up_node[B][i]) { A = up_node[A][i]; B = up_node[B][i]; } } return up_node[A][0]; } int main() { ios_base::sync_with_stdio(false); int n; cin >> n; depth[0] = 0; parent[0] = 0; vector
queries(n + 1, -1); vector
> > find_LCA; for(int i = 1; i <= n; i++) { char c; cin >> c; if(c == 'a') { int x; cin >> x; x = id_node[x]; id_node[i] = i; parent[i] = x; depth[i] = depth[parent[i]] + 1; } else if(c == 'b') { int x; cin >> x; x = id_node[x]; id_node[i] = parent[x]; queries[i] = x; } else if(c == 'c') { int x, y; cin >> x >> y; x = id_node[x]; y = id_node[y]; id_node[i] = x; find_LCA.push_back(make_pair(i, make_pair(x, y))); } } for(int i = 0; i <= n; i++) { up_node[i][0] = parent[i]; for(int j = 1; j < logn; j++) { up_node[i][j] = up_node[up_node[i][j - 1]][j - 1]; } } for(int i = 0; i < find_LCA.size(); i++) { int a = find_LCA[i].second.first; int b = find_LCA[i].second.second; queries[find_LCA[i].first] = depth[LCA(a, b)]; } for(int i = 1; i <= n; i++) { if(queries[i] != -1) { cout << queries[i] << endl; } } return 0; } /* 12 1 2 2 4 2 5 4 7 5 8 1 3 3 6 6 9 6 10 6 11 11 12 **/
Mark as private (unlisted)
for 30 minutes
for 6 hours
for 1 day
for 1 week
for 1 month
for 1 year
everlasting (like CCCP)