BOJ 17306 - 전쟁 중의 삶

BOJ 17306 - 전쟁 중의 삶

노드의 번호가 $1 \le i < 2^{50}$ 이므로 최대 $O(50N)$ 개의 노드만 보면 된다.

DFS를 돌리며,

• 자신의 부모 노드쪽에 노드가 존재하는가?
• 현재 자신의 번호에 군대가 존재하는가?
• 자신의 왼쪽 서브트리와 오른쪽 서브트리에 군대가 존재하는가?

정보를 모두 알 수 있다면 자신이 정답에 포함이 되어야 할 지 알 수 있다.

일단 현재 노드의 서브트리가 비어있지 않다고 하자.

• 자신이 포함이 되거나, 부모쪽에 군대를 가진 노드가 존재하거나, 자신의 두 자식 모두에 군대가 존재하거나 하면 자신은 포함되어야 한다.

이제 이걸 잘 구현해주면 되는데, 지랄맞은 std::set 같은거 써서 채점현황에 레드카펫 깔지말고 직접 트라이를 구현해주는 것으로 해결 가능하다.

int get_level(ll i) {  
   int level = 0;  
   ll cur = 1;  
   while (cur * 2 <= i) level++, cur *= 2;  
   return level;  
}  
  
int n;  
ll pw2[55];  
struct trie {  
   ll cur;  
   int level;  
   bool cur_in = 0;  
   trie *l = 0, *r = 0;  
  
   trie(ll cur, int level) : cur(cur), level(level) {}  
  
   void insert(ll i, int lv) {  
      if (i == cur) {  
         cur_in = 1;  
         return;  
      }  
  
      ll left = cur * pw2[lv - level];  
      ll right = left + pw2[lv - level - 1];  
      if (i < right) {  
         if (l == 0) l = new trie(cur * 2, level + 1);  
         l->insert(i, lv);  
      } else {  
         if (r == 0) r = new trie(cur * 2 + 1, level + 1);  
         r->insert(i, lv);  
      }  
   }  
  
   int query(int from_top) {  
      bool lc = l != 0;  
      bool rc = r != 0;  
      int ret = 0;  
      if (from_top || cur_in || lc && rc) ret++;  
      if (lc) ret += l->query(from_top | cur_in | rc);  
      if (rc) ret += r->query(from_top | cur_in | lc);  
      return ret;  
   }  
};  
  
void solve() {  
   pw2[0] = 1;  
   for (int i = 1; i <= 54; i++) pw2[i] = pw2[i - 1] * 2;  
  
   cin >> n;  
   ll u;  
  
   trie *root = new trie(1, 0);  
   for (int i = 0; i < n; i++) {  
      cin >> u;  
      root->insert(u, get_level(u));  
   }  
   cout << root->query(0);  
}