부동산 다툼 20364

문제

접근 방법

트리에서 2로 나눌 경우 부모의 인덱스이다.
해당 문제는 다른 오리가 내 노드 위에 존재하는지 확인하는 문제이다.
2로 계속 나눈 다음 이미 점유했다면 해당 번호를 기록해 준다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<bool> isVisited;
int N, Q, x, parent, visitedParent;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> Q;
    isVisited = vector<bool>(N + 1);
    while (Q--)
    {
        cin >> x;
        parent = x;
        visitedParent = N + 1;
        while (parent)
        {
            if (isVisited[parent])
                visitedParent = parent;
            parent >>= 1;
        }
        if (visitedParent == N + 1)
        {
            isVisited[x] = true;
            cout << 0;
        }
        else
        {
            cout << visitedParent;
        }
        cout << "\n";
    }
    return 0;
}

풀이

꽤 괜찮게 푼 것 같다.

처음 마주치는 점유된 땅의 번호를 알아야 하므로 도중에 만나더라도 멈추지 않고 계속 진행해 줘야 한다.