Home PAT 1143 Lowest Common Ancestor
Post
Cancel

PAT 1143 Lowest Common Ancestor

Link

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <unordered_map>
using namespace std;
#define N 10010
int m,n;
unordered_map<int,int>keymap;
int pre[10010],father[10010];
bool v[10010];
void build(int left,int right){
    if(left>=right) return;
    int i=left+1;
    for(;i<=right;++i)
        if(pre[i]>=pre[left])
            break;
    if(i<=right){
        father[keymap[pre[left+1]]]=keymap[pre[left]];
        father[keymap[pre[i]]]=keymap[pre[left]];
        build(left+1,i-1);
        build(i,right);
    }else{
        father[keymap[pre[left+1]]]=keymap[pre[left]];
        build(left+1,right);
    }
}
void LCA(int v1,int v2){
    memset(v,false,sizeof(v));
    int u1=v1,u2=v2;
    while(v1){
        v[v1]=true;
        v1=father[v1];
    }
    while(v2){
        if(v[v2]) break;
        v2=father[v2];
    }
    if(v2==u1) printf("%d is an ancestor of %d.\n",pre[u1],pre[u2]);
    else if(v2==u2) printf("%d is an ancestor of %d.\n",pre[u2],pre[u1]);
    else  printf("LCA of %d and %d is %d.\n",pre[u1],pre[u2],pre[v2]);
}
int main() {
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&pre[i]);
        keymap[pre[i]]=i;
    }
    build(1,n);
    while(m--){
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        bool f1=true,f2=true;
        if(keymap.count(v1)==0) f1=false;
        if(keymap.count(v2)==0) f2=false;
        if(!f1&&f2) printf("ERROR: %d is not found.\n",v1);
        else if(f1&&!f2) printf("ERROR: %d is not found.\n",v2);
        else if(!f1&&!f2) printf("ERROR: %d and %d are not found.\n",v1,v2);
        else LCA(keymap[v1],keymap[v2]);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.