ZROI#1013
看起来以为是个 $Floyd$ 传递闭包…
一看数据范围,算了叭.这拿头过啊.
一拿过来肯定缩点嘛.
缩完点成为一个 $DAG$ , 一般 $DAG$ 先考虑考虑拓扑排序后再做.
那么这个题怎么考虑拓扑呢?暂时还没有思路.
但我们发现,如果我们有一条边 $(u,v)$ , 那么 $v$ 能达到的点, $u$ 也一定能到达,因为 $u$ 能到达 $v$.
如果我们把每个点能到的点视为一个二进制状态,那么显然有 $status_u = status_u | status_v$
那么这是显然可以一路递推的,怎么递推呢?逆拓扑!
总体思路呼之欲出了 $:$
先缩点成为一个 $DAG$ , 再对 $DAG$ 做拓扑,以逆拓扑的顺序递推得到每个点的状态,查询直接查询对应位即可.
但我们发现这样很不行,因为共有 $2\times 10^5$ 个点,每个点都要开这么大二进制状态,开出来人都没了.
不如你每 $64$ 个点压一个 $unsigned \: long \: long$ 然后每个点只需要至多 $\cfrac{n}{64}$ 个 $ull$ 就能存下,这样的空间就可以负担的起了.
那么怎么实现呢?一个简单的方法是指针实现,开一个长度为 $1e8$ 的内存池.
对每个点及其所需空间顺次放入,用一个 $2\times 10^5$ 的指针数组指向每个点的起始位置,然后空出 $\cfrac{n}{64}$ 个位置留作第二维.
这样,我们要在点 $u$ 的状态中找一个点 $v$ , 只需要把 $v$ 对应的编号除以 $64$ 得到它是在 $u$ 之后的第几个位置,然后再和对应的位数取 $\&$ 即可.
$Code:$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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;
struct ios {
inline char gc(){
static const int IN_LEN=1<<18|1;
static char buf[IN_LEN],*s,*t;
return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
}
template <typename _Tp> inline ios & operator >> (_Tp&x){
static char ch,sgn; ch = gc(), sgn = 0;
for(;!isdigit(ch);ch=gc()){if(ch==-1)return *this;sgn|=ch=='-';}
for(x=0;isdigit(ch);ch=gc())x=x*10+(ch^'0');
sgn&&(x=-x); return *this;
}
} io;
const int N = 2e5 + 100 ;
const int M = 1e8 + 100 ;
const int E = 1e6 + 100 ;
struct edge { int to , next ; } e[E] , G[E] ;
queue < int > q ;
int n , m , qs , ind[N] , dfn[N] , low[N] , top , L , head1[N] ;
int idx[N] , siz[N] , cnt , tot , s[N] , tot1 , tot2 , head2[N] ;
ull *now , *bit[N] , pool[M] ; bool ins[N] ;
inline void tarjan (int cur) {
s[++top] = cur ; ins[cur] = true ;
dfn[cur] = low[cur] = ++ cnt ;
for (int i = head1[cur] ; i ; i = e[i].next) {
int k = e[i].to ;
if ( ! dfn[k] ) {
tarjan ( k ) ;
low[cur] = std::min ( low[cur] , low[k] ) ;
} else if ( ins[k] ) low[cur] = std::min ( low[cur] , dfn[k] ) ;
}
if ( low[cur] == dfn[cur] ) {
while ( s[top+1] != cur ) {
idx[s[top]] = tot ;
++ siz[tot] ;
ins[s[top--]] = false ;
}
++ tot ;
}
return ;
}
inline void update (int x , int y) { rep ( i , 0 , L - 1 ) bit[y][i] |= bit[x][i] ; return ; }
inline void build (int u , int v ) {
e[++tot1].next = head1[u] ;
e[tot1].to = v ; head1[u] = tot1 ;
}
inline void _build (int u , int v ) {
G[++tot2].next = head2[u] ;
G[tot2].to = v ; head2[u] = tot2 ;
}
signed main (int argc , char * argv[]) {
io >> n >> m >> qs ;
rep ( i , 1 , m ) { int u , v ; io >> u >> v ; build ( u , v ) ; }
rep ( i , 1 , n ) if ( ! dfn[i] ) tarjan ( i ) ;
rep ( i , 1 , n ) for (int j = head1[i] ; j ; j = e[j].next) {
int k = e[j].to ;
if ( idx[i] != idx[k] ) { _build ( idx[k] , idx[i] ) ; ++ ind[idx[i]] ; }
}
now = pool ; L = ( tot + 63 ) / 64 ;
rep ( i , 0 , tot - 1 ) {
bit[i] = now ; now += L ;
bit[i][i>>6] |= 1ull << ( i & 63 ) ;
}
while ( ! q.empty () ) q.pop () ;
rep ( i , 0 , tot - 1 ) if ( ! ind[i] ) q.push ( i ) ;
while ( ! q.empty () ) {
int j = q.front () ; q.pop () ;
for (int i = head2[j] ; i ; i = G[i].next) {
int k = G[i].to ;
-- ind[k] ; update ( j , k ) ;
if ( ! ind[k] ) q.push ( k ) ;
}
}
while ( qs -- ) {
int u , v ; io >> u >> v ; u = idx[u] ; v = idx[v] ;
if ( ( bit[u][v>>6] >> ( v & 63 ) ) & 1 ) puts ("Yes") ;
else puts ("No") ;
}
system ("pause") ; return 0 ;
}