import java.io.*; import java.util.*; public class Main { /* * N명의 사람이 주어진다. * 이야기의 진실을 아는 사람이 주어진다. * * 파티에 오는 사람들의 번호가 주어진다. * - 지민이는 모든 파티에 참가한다. * * 지민이가 거짓말쟁이로 알려지지 않으면서 과장된 이야기를 할 수 있는 파티의 갯수를 구하라 * * 파티에 어떤 이야기의 진실을 아는 사람이 없는 경우 과장된 이야기를 할 수 있다. * - 단, 임의 사람이 어떤 파티에서는 과장된 이야기, 어떤 파티에서는 진실을 듣게되면 안된다. * * 사람과 파티의 최대는 50 * * 완탐 * 비트마스킹 * union-find */ static int numOfPerson; static int numOfParty; static int numOfTruth; static int answer; static int[] arrOfParent; static void union(int left, int right) { int parentLeft = find(left); int parentRight = find(right); // 부모가 같으면 합치지 않아도 된다. if (parentLeft == parentRight) { return; } if (parentLeft <= parentRight) { arrOfParent[parentRight] = parentLeft; } else { arrOfParent[parentLeft] = parentRight; } } static int find(int child) { if (arrOfParent[child] == child) { return child; } return arrOfParent[child] = find(arrOfParent[child]); } static void inputData() throws IOException { answer = 0; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; st = new StringTokenizer(br.readLine().trim()); numOfPerson = Integer.parseInt(st.nextToken()); numOfParty = Integer.parseInt(st.nextToken()); // union-find를 위한 준빈 arrOfParent = new int[numOfPerson + 1]; for (int idx = 0; idx <= numOfPerson; idx++) { arrOfParent[idx] = idx; } st = new StringTokenizer(br.readLine().trim()); numOfTruth = Integer.parseInt(st.nextToken()); // 최초 비밀을 알고 있는 사람들 ArrayList truthList = new ArrayList<>(); if (numOfTruth != 0) { for (int idx = 0; idx < numOfTruth; idx++) { int truth = Integer.parseInt(st.nextToken()); truthList.add(truth); } } long[] party = new long[numOfParty]; // 파티에 참여하는 사람 for (int idx = 0; idx < numOfParty; idx++) { st = new StringTokenizer(br.readLine().trim()); // 파티에 참여하는 사람수 int total = Integer.parseInt(st.nextToken()); int std = -1; for (int personIdx = 0; personIdx < total; personIdx++) { int person = Integer.parseInt(st.nextToken()); // 파티에 참여하는 사람 체크 party[idx] = party[idx] | (1 << person); if (std == -1) { std = person; continue; } // 비밀을 공유할 가능성이 있는 사람의 합집합 만들기 union(std, person); } } // 진실을 알고 있는 사람들 최종 정리 // 최초 진실을 알고 있는 사람에 부모을 비트마스킹 long truthBit = 0L; for (Integer truth : truthList) { truthBit = truthBit | (1 << arrOfParent[truth]); } // 모든 자식에 대해서 진실을 알고 있는지 확인 후 비트마스킹 for (int idx = 1; idx <= numOfPerson; idx++) { if ((truthBit & (1 << arrOfParent[idx])) == (1 << arrOfParent[idx])) { truthBit = truthBit | (1 << idx); } } // System.out.println(Long.toBinaryString(truthBit)); // 파티 인원과 진실을 알고 있는 인원 중 겹치는 인원이 있는지 체크 for (int idx = 0; idx < numOfParty; idx++) { if (!((party[idx] & truthBit) > 0)) { answer++; } } } public static void main(String[] args) throws IOException { inputData(); System.out.println(answer); } }

제출 #34475

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력: