library/test/aoj/GRL_5_C-LCA_Lowest_Common_Ancestor.lca.test.cpp

• View this file on GitHub
• Last update: 2024-03-15 16:42:38+06:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C

Depends on

• library/graph/lca.hpp

Code

#include <bits/stdc++.h>
using namespace std;
#include "../../graph/lca.hpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C"

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<vector<int>> G(n);
    for(int i=0; i<n; ++i) {
        int k;
        cin>>k;
        for(int j=0; j<k; ++j) {
            int c;
            cin>>c;
            G[i].push_back(c);
            G[c].push_back(i);
        }
    }

    LCA lca(G, 0);

    int q;
    cin>>q;
    while(q--) {
        int a, b;
        cin>>a>>b;
        cout<<lca.query(a, b)<<'\n';
    }
    return 0;
}

#line 1 "library/test/aoj/GRL_5_C-LCA_Lowest_Common_Ancestor.lca.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#line 2 "library/graph/lca.hpp"

struct LCA {
    vector<vector<int>> parent;
    vector<int> depth;
    LCA() {}
    LCA(const vector<vector<int>>& G, int r = 0) { init(G, r); }

    void init(const vector<vector<int>>& G, int r = 0) {
        int V = (int)G.size();
        int h = 1;
        while ((1 << h) < V) ++h;
        parent.assign(h, vector<int>(V, -1));
        depth.assign(V, -1);
        dfs(G, r, -1, 0);
        for (int i = 0; i + 1 < (int)parent.size(); ++i) {
            for (int v = 0; v < V; ++v) {
                if (parent[i][v] != -1) {
                    parent[i + 1][v] = parent[i][parent[i][v]];
                }
            }
        }
    }

    void dfs(const vector<vector<int>>& G, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (auto e : G[v])
            if (e != p) dfs(G, e, v, d + 1);
    }

    int query(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        for (int i = 0; i < (int)parent.size(); ++i) {
            if ((depth[v] - depth[u]) & (1 << i)) v = parent[i][v];
        }
        if (u == v) return u;
        for (int i = (int)parent.size() - 1; i >= 0; --i) {
            if (parent[i][u] != parent[i][v]) {
                u = parent[i][u];
                v = parent[i][v];
            }
        }
        return parent[0][u];
    }

    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[query(u, v)];
    }

    bool is_on_path(int u, int v, int x) {
        return dist(u, x) + dist(x, v) == dist(u, v);
    }
};
#line 4 "library/test/aoj/GRL_5_C-LCA_Lowest_Common_Ancestor.lca.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_5_C"

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    vector<vector<int>> G(n);
    for(int i=0; i<n; ++i) {
        int k;
        cin>>k;
        for(int j=0; j<k; ++j) {
            int c;
            cin>>c;
            G[i].push_back(c);
            G[c].push_back(i);
        }
    }

    LCA lca(G, 0);

    int q;
    cin>>q;
    while(q--) {
        int a, b;
        cin>>a>>b;
        cout<<lca.query(a, b)<<'\n';
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.in	AC	6 ms	4 MB
g++	01_small_00.in	AC	5 ms	4 MB
g++	02_middle_00.in	AC	5 ms	4 MB
g++	02_middle_01.in	AC	5 ms	4 MB
g++	02_middle_02.in	AC	6 ms	4 MB
g++	02_middle_03.in	AC	5 ms	4 MB
g++	03_corner_00.in	AC	5 ms	4 MB
g++	03_corner_01.in	AC	5 ms	4 MB
g++	04_rand_00.in	AC	5 ms	4 MB
g++	04_rand_01.in	AC	5 ms	4 MB
g++	04_rand_02.in	AC	5 ms	4 MB
g++	04_rand_03.in	AC	6 ms	4 MB
g++	04_rand_04.in	AC	6 ms	4 MB
g++	04_rand_05.in	AC	5 ms	4 MB
g++	04_rand_06.in	AC	6 ms	4 MB
g++	04_rand_07.in	AC	6 ms	4 MB
g++	05_complete_00.in	AC	5 ms	4 MB
g++	05_complete_01.in	AC	5 ms	4 MB
g++	05_complete_02.in	AC	6 ms	4 MB
g++	05_complete_03.in	AC	6 ms	4 MB
g++	05_complete_04.in	AC	7 ms	4 MB
g++	05_complete_05.in	AC	8 ms	4 MB
g++	05_complete_06.in	AC	16 ms	4 MB
g++	05_complete_07.in	AC	30 ms	9 MB
g++	06_biased_00.in	AC	138 ms	5 MB
g++	06_biased_01.in	AC	154 ms	19 MB
g++	06_biased_02.in	AC	174 ms	16 MB
g++	06_biased_03.in	AC	159 ms	17 MB
g++	07_large_00.in	AC	167 ms	16 MB
g++	07_large_01.in	AC	177 ms	16 MB
g++	07_large_02.in	AC	183 ms	16 MB
g++	07_large_03.in	AC	173 ms	16 MB

Back to top page