Two points timeout, there is no choice to build the tree first, may lead to too much recursion, so timeout, code:
#include<iostream>
#include<set>
#include<vector>
using namespace std;
set<int> se;
int a[10010];
int b[10010];
int n1,n2;
set<int> father;
vector<int> v;
bool f1=false,f2=false;
void func1(int l1,int r1,int l2,int r2,int aim,int t2){
int t=l2;
for(t;t<=r2&&b[t]!=a[l1];t++);
if(aim<b[t]){
if(b[t]==t2){f1=true;return;}
father.insert(b[t]);
func1(l1+1,t-l2+l1,l2,t-1,aim,t2);
}
else if(aim>b[t]){
if(b[t]==t2){f1=true;return;}
father.insert(b[t]);
func1(l1+t-l2+1,r1,t+1,r2,aim,t2);
}
return;
}
void func2(int l1,int r1,int l2,int r2,int aim,int t1){
int t=l2;
for(t;t<=r2&&b[t]!=a[l1];t++);
if(aim<b[t]){
if(b[t]==t1){f2=true;return;}
v.push_back(b[t]);
func2(l1+1,t-l2+l1,l2,t-1,aim,t1);
}
else if(aim>b[t]){
if(b[t]==t1){f2=true;return;}
v.push_back(b[t]);
func2(l1+t-l2+1,r1,t+1,r2,aim,t1);
}
return;
}
int main(){
cin>>n1>>n2;
for(int i=0;i<n2;i++){
cin>>a[i];
se.insert(a[i]);
}
auto it=se.begin();
for(int i=0;i<n2;i++){
b[i]=*it;
it++;
}
for(int i=0;i<n1;i++){
f1=false;f2=false;
int t1,t2;
cin>>t1>>t2;
if(se.find(t1)==se.end()&&se.find(t2)==se.end()){
cout<<"ERROR: "<<t1<<" and "<<t2<<" are not found."<<endl;
continue;
}
else if(se.find(t1)==se.end()&&se.find(t2)!=se.end()){
cout<<"ERROR: "<<t1<<" is not found."<<endl;
continue;
}
else if(se.find(t1)!=se.end()&&se.find(t2)==se.end()){
cout<<"ERROR: "<<t2<<" is not found."<<endl;
continue;
}
if(t1==t2){
cout<<t1<<" is an ancestor of "<<t1<<"."<<endl;
continue;
}
father.clear();
v.clear();
father.insert(a[0]);
v.push_back(a[0]);
func1(0,n2-1,0,n2-1,t1,t2);
if(f1){
cout<<t2<<" is an ancestor of "<<t1<<"."<<endl;
continue;
}
func2(0,n2-1,0,n2-1,t2,t1);
if(f2){
cout<<t1<<" is an ancestor of "<<t2<<"."<<endl;
continue;
}
for(int i=v.size()-1;i>=0;i--){
if(father.find(v[i])!=father.end()){
cout<<"LCA of "<<t1<<" and "<<t2<<" is "<<v[i]<<"."<<endl;
break;
}
}
}
return 0;
}
Read More:
- Error: php56w-common conflicts with php-common-5.3.3-48.el6_ 8.x86_ 64
- Common causes of Leetcode Runtime Error
- Common attributes and methods of list and map in Dar
- One of the common mistakes of tex
- Verilog testbench common blocks
- R-common errors and their possible causes — Notes
- Several common methods of inserting pictures into latex documents
- C + + common errors: “error: XXX in namespace ‘STD’ does not name a template type”
- Linux common problems and Solutions
- OpenGL development environment configuration [vs2017] + common problems
- What are the common clearing commands in MATLAB?
- Summary of common runtimeException exceptions
- Common problems and solutions under Linux
- Common errors and modification methods of findbug
- Common faults and solutions of sylixos IDE (1)
- Common command of docker
- Some common problems in the use of vs2017
- Common errors and solutions of Qt development application under Ubuntu
- Common problems of shadow map in OpenGL
- Summary of common errors in angularjs