1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
using namespace std;
struct {
char buf[1 << 21], *st = buf, *en = buf;
#define gc() (st == en && (st = buf, en = buf + fread(buf, 1, 1 << 21, stdin), st == en) ? EOF : *(st++))
inline operator int () {
int a = 0, c;
for(c = gc(); c < '0' || c > '9'; c = gc());
for(; c >= '0' && c <= '9'; c = gc()) a = (a << 1) + (a << 3) + (c ^ '0');
return a;
}
} input;
typedef bitset<1001> bs;
pair<int, int> ed[200010];
int buf[200010];
int *son[1010], cnt[1010], n, m, k;
inline void build_g() {
sort(ed, ed + m * 2);
for(int i = 0; i < m * 2; i++) buf[i] = ed[i].second;
for(int l = 0, r = -1; l < m * 2; l = r + 1) {
for(; r < m * 2 && ed[r + 1].first == ed[l].first; r++);
son[ed[l].first] = buf + l;
cnt[ed[l].first] = r - l + 1;
}
}
int dis[1010];
inline void bfs(int s) {
memset(dis, 0x3f, sizeof dis);
queue<int> q;
q.push(s);
dis[s] = 0;
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i = 0; i < cnt[now]; i++)
if(dis[son[now][i]] > dis[now] + 1)
dis[son[now][i]] = dis[now] + 1, q.push(son[now][i]);
}
}
int id[1010];
inline int cmp(int a, int b) {
return dis[a] < dis[b];
}
vector<pair<int, int> > q[1010];
bs ans[100010], tmp;
int main() {
n = input;
m = input;
k = input;
for(int i = 0; i < m; i++)
ed[i << 1].first = ed[i << 1 | 1].second = input,
ed[i << 1].second = ed[i << 1 | 1].first = input;
build_g();
for(int i = 0; i < k; i++) {
for(int a = input; a--; ) {
int x = input, y = input;
q[x].push_back(make_pair(y, i));
}
}
for(int i = 1; i <= n; i++) id[i] = i;
for(int i = 1; i <= n; i++) {
bfs(i);
sort(q[i].begin(), q[i].end());
tmp.reset();
sort(id + 1, id + 1 + n, cmp);
for(int t = 1, j = 0; j < q[i].size(); j++) {
for(; t <= n && dis[id[t]] <= q[i][j].first; t++) tmp.set(id[t]);
ans[q[i][j].second] |= tmp;
}
}
for(int i = 0; i < k; i++) printf("%dn", ans[i].count());
return 0;
}
|
近期评论