글 읽기 - [c++] 틀렸습니다.. 혹시 반례가 있을까요?? 코드 한번만 봐주세요..ㅠㅠ

tizm423 3년 전 2

세그먼트 트리를 이용해서 풀어보려했습니다.

전위탐색 시킬 때 왼쪽노드를 먼저 방문하고 오른쪽 노드를 방문하는데 그 사이에 부모노드를 한번 더 넣어준것이 tour입니다.

여기서 각 노드가 tour에서 처음 나타난 부분을 locInTour에 저장시켰습니다.

세그먼트 트리는 tour에 있는 노드로 만드는데, 깊이가 가장 낮은 노드를 트리에 저장시켰습니다.

따라서 a와 b를 입력받고, 이 노드가 tour에서 처음 나타난 부분을 구간으로 잡아 세그먼트 트리에 쿼리를 날리면

LCA를 받는다고 생각하고 풀었습니다.

혹시 제가 코드를 잘못짠걸까요??

틀린부분이 있으면 지적 부탁드립니다!!!

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 50001;
vector<int> child[MAX_N];
vector<int> tour;
int locInTour[MAX_N];
int depth[MAX_N];

int init(vector<int>& tree, vector<int>& arr, int node, int start, int end){
    if(start == end) return tree[node] = arr[start];
    else {
        int leftNode = init(tree, arr, node*2, start, (start+end)/2);
        int rightNode = init(tree, arr, node*2+1, (start+end)/2+1, end);
        return depth[leftNode] < depth[rightNode] ? tree[node] = leftNode : tree[node] = rightNode;
    }
}

int query(vector<int>& tree, int node, int start, int end, int left, int right) {
    if(start > right || end < left) return -1;
    if(left <= start && end <= right) return tree[node];
    int leftNode = query(tree, node*2, start, (start+end)/2, left, right);
    int rightNode = query(tree, node*2+1, (start+end)/2+1, end, left, right);
    if(leftNode == -1) return rightNode;
    if(rightNode == -1) return leftNode;
    return depth[leftNode] < depth[rightNode] ? leftNode : rightNode;
}

void buildTour(int node, int d){
    depth[node] = d;

    locInTour[node] = tour.size(); 
    tour.push_back(node);

    int N = child[node].size();
    for(int i=0; i<N; i++) {
        buildTour(child[node][i], d+1);
        tour.push_back(node);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    for(int i=1; i<N; i++){
        int a, b;
        cin >> a >> b;
        if(a > b) swap(a, b);
        child[a].push_back(b);
    }

    buildTour(1, 0);
    int s = tour.size();
    vector<int> tree(4*s);
    init(tree, tour, 1, 0, s-1);

    int M;
    cin >> M;
    while(M--){
        int a, b;
        cin >> a >> b;
        int la = locInTour[a];
        int lb = locInTour[b];
        if(la > lb) swap(la, lb);
        cout << query(tree, 1, 0, s-1, la, lb) << '\n';
    }
}

dpjungmin 3년 전 1

두 노드가 연결된 경우 "번호가 낮은 노드가 부모 노드일 것이다" 라는 가정을 한 것이 잘못된 것 같습니다.

트리의 연결상태를 입력받는 부분과 buildTour 함수를 조금만 손보면 될 것 같습니다.

수정된 코드는 아래와 비슷할 것 같습니다.

#include <iostream>
#include <vector>
using namespace std;

const int MAX_N = 50001;
vector<int> child[MAX_N];
vector<int> tour;
int locInTour[MAX_N];
int depth[MAX_N];

int init(vector<int>& tree, vector<int>& arr, int node, int start, int end){
    if(start == end) return tree[node] = arr[start];
    else {
        int leftNode = init(tree, arr, node*2, start, (start+end)/2);
        int rightNode = init(tree, arr, node*2+1, (start+end)/2+1, end);
        return depth[leftNode] < depth[rightNode] ? tree[node] = leftNode : tree[node] = rightNode;
    }
}

int query(vector<int>& tree, int node, int start, int end, int left, int right) {
    if(start > right || end < left) return -1;
    if(left <= start && end <= right) return tree[node];
    int leftNode = query(tree, node*2, start, (start+end)/2, left, right);
    int rightNode = query(tree, node*2+1, (start+end)/2+1, end, left, right);
    if(leftNode == -1) return rightNode;
    if(rightNode == -1) return leftNode;
    return depth[leftNode] < depth[rightNode] ? leftNode : rightNode;
}

void buildTour(int node, int par, int d){
    depth[node] = d;

    locInTour[node] = tour.size(); 
    tour.push_back(node);

    int N = child[node].size();
    for(int i=0; i<N; i++) {
        if (child[node][i] == par) continue;
        buildTour(child[node][i], node, d+1);
        tour.push_back(node);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    for(int i=1; i<N; i++){
        int a, b;
        cin >> a >> b;
        child[a].push_back(b);
        child[b].push_back(a);
    }

    buildTour(1, 1, 0);
    int s = tour.size();
    vector<int> tree(4*s);
    init(tree, tour, 1, 0, s-1);

    int M;
    cin >> M;
    while(M--){
        int a, b;
        cin >> a >> b;
        int la = locInTour[a];
        int lb = locInTour[b];
        if(la > lb) swap(la, lb);
        cout << query(tree, 1, 0, s-1, la, lb) << '\n';
    }
}

tizm423 3년 전 2

@dpjungmin 님 정말 감사합니다..

가장 기본적인 부분에서 실수했네요..ㅠㅠ

몇일동안 고생했는데 덕분에 깔끔하게 해결됐습니다. 정말 감사합니다!!

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

문제

문제

출처

ICPC

[c++] 틀렸습니다.. 혹시 반례가 있을까요?? 코드 한번만 봐주세요..ㅠㅠ

tizm423 3년 전 2

dpjungmin 3년 전 1

tizm423 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말