글 읽기 - LCA test case가 더 있을까요?

jth 5년 전 1

안녕하세요 ~ 항상 도움주셔서 감사합니다.

오일러 투어랑 세그먼트 트리 사용해서 O(N+MlogN) 만에 구현을 해보았는데요, 예제 및 질문 검색 게시판에 있는 테스트 케이스들을 다 통과하는데 문제 통과를 못하고 있네요 ㅎㅎ 혹시 틀릴만한 구석이 더 있을까요?

답변 감사드립니다 !

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int N, M;
int idx[50001], euler[500001], level[500001];
int k;

struct node {
    vector<int> childs;
} nodes[50001]; // node 1: root.

struct st {
    int size;
    int *tree;
    st(int n) {
        size = n;
        int h = (int)ceil(log2(n));
        tree = new int[1<<(h+1)];
        init(1, 0, size-1);
    }
    int init(int now, int s, int e) {
        if(s==e) return tree[now] = s;
        int left = init(2*now, s, (s+e)/2);
        int right = init(2*now+1, (s+e)/2+1, e);
        return tree[now] = level[left]<=level[right]? left:right;
    }
    // return idx that has minimum level at given range.
    int qry(int l, int r, int now, int s, int e) {
        if(l>e||r<s) return -1;
        if(l<=s&&e<=r) return tree[now];
        int left = qry(l, r, 2*now, s, (s+e)/2);
        int right = qry(l, r, 2*now+1, (s+e)/2+1, e);
        if(left==-1||right==-1) return left==-1? right:left;
        else return level[left]<=level[right]? left:right;
    }
};

void euler_tour(int now, int depth) {
    euler[k] = now, level[k] = depth;
    idx[now] = k++;
    for(auto c: nodes[now].childs) {
        euler_tour(c, depth+1);
        euler[k] = now, level[k] = depth;
        k++;
    }
}

int max(int a, int b) { return a>b? a:b; }
int min(int a, int b) { return a<b? a:b; }

int main() {

    int a, b;

    scanf("%d", &N);
    vector<vector<int>> graph(N+1);
    for(int i=0; i<N-1; i++) {
        scanf("%d%d", &a, &b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    bool visited[N+1];
    for(int i=0; i<N+1; i++) visited[i] = 0;
    for(int i=1; i<N+1; i++) {
        visited[i] = 1;
        for(auto adj: graph[i]) {
            if(visited[adj]) continue;
            nodes[i].childs.push_back(adj);
        }
    }

    k = 0;
    euler_tour(1, 0);
    st seg_tree(k);

    scanf("%d", &M);
    for(int i=0; i<M; i++) {
        scanf("%d%d", &a, &b);
        int ii = seg_tree.qry(min(idx[a],idx[b]), max(idx[a], idx[b]), 1, 0, k-1);
        printf("%d\n", euler[ii]);
    }

    return 0;
}

jth 5년 전 2

해결했습니다! LCA 자체에 오류가 있는 것이 아니고, tree를 generate 하는 부분에서 오류가 있었습니다 .

아래처럼 재귀적으로 호출해주어서 이 문제를 해결하였습니다 ~

void generate(int i) {
    visited[i] = 1;
    for(auto adj: graph[i]) {
        if(visited[adj]) continue;
        nodes[i].childs.push_back(adj);
        generate(adj);
    }
}

dbfldkfdbgml 4년 전 0

최소공통 조상 오일러 투어 + 인덱스 트리는 처음이네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

LCA test case가 더 있을까요?

jth 5년 전 1

jth 5년 전 2

dbfldkfdbgml 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말