POJ 2443 - Set Operation

http://poj.org/problem?id=2443

概要

N 個の集合があり，i 番目の集合は C(i) 個の正の整数からなっている．

Q 個の「正の整数 x, y のどちらも要素として含んでいる集合は存在するか？」というクエリに答える．

制約

• 1 <= N <= 1000
• 1 <= C(i) <= 10000
• 1 <= Q <= 200000
• 1 <= 各要素の値 <= 10000

解法

正の整数 n が i 番目の集合に属していることを a[n][i] で持って，各クエリに対して a[x][k] && a[y][k] なる k が存在するかどうか調べる． O(QN) = 10^8 だけどこれで通る (1313MS)．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N;
 7   scanf("%d", &N);
 8   static bool a[10000][1000];
 9   for (int i = 0; i < N; i++) {
10     int C;
11     scanf("%d", &C);
12     for (int j = 0; j < C; j++) {
13       int x;
14       scanf("%d", &x);
15       --x;
16       a[x][i] = true;
17     }
18   }
19 
20   int Q;
21   scanf("%d", &Q);
22   while (Q-- > 0) {
23     int x, y;
24     scanf("%d %d", &x, &y);
25     --x;  --y;
26     bool ok = false;
27     for (int i = 0; i < N; i++) {
28       if (a[x][i] && a[y][i]) {
29         ok = true;
30         break;
31       }
32     }
33     puts(ok ? "Yes" : "No");
34   }
35   return 0;
36 }