테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== Facebook ======

===== 풀이 =====
  * a,b가 주어졌을때 공통된 이웃을 그냥 세려면 O(N)이 걸리지만, 비트셋을 이용하면 O(N/w)로 단축시킬수 있다. [[ps:tutorial:부분그래프 세기#C3 세기|그래프에서 삼각형 세기]]에서도 설명한 방법이다. 이렇게 하면 총 시간복잡도는 O(QN/w)가 된다.
  * 입력을 비트셋으로 변환할때에는 그냥 입력 자체가 2진수라고 생각해서, 바로 int함수를 써서 변환하면 간단하다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 20501. Facebook".

- Problem link: https://www.acmicpc.net/problem/20501
- Solution link: http://www.teferi.net/ps/problems/boj/20501

Tags: [bitset]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    friends = [int(sys.stdin.readline(), 2) for _ in range(N)]
    Q = int(sys.stdin.readline())
    for _ in range(Q):
        a, b = [int(x) - 1 for x in sys.stdin.readline().split()]
        print((friends[a] & friends[b]).bit_count())


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}